......................

Shell Sort

Posted by Ankit Pokhrel On Friday, September 3, 2010 2 comments

/***************************************************************************
Shell sort is a sorting algorithm, devised by Donald Shell in 1959, that is a generalization of insertion
sort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted.
It improves on insertion sort by allowing the comparison and exchange of elements that are far apart.
The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be
almost sorted.

-------------------------------
SHELL SORT ALGORITHM
-------------------------------
input: an array num of length n with array elements numbered 0 to n - 1

Shell.Sort(num,n,key)
1. Assign, span = int(n/2)
2. while span > 0 do:
   a) for i from span to n - 1, Repeat step b,c,e
   b) assign num[i] to key and i to j
   c) while j = span and num[j - span] > key, Repeat step d
   d) swap num[j] and num[j - span]
   e) Assign, span = int(span / 2.2)
3. Use Insertion Sort to sort remaining array of data
----------------------------------------------------------------------------

The following is an implementation of Shell sort written in pseudocode.
The increment sequence is a geometric sequence in which every term is
roughly 2.2 times smaller than the previous one:
---------------------
SHELL SORT PSEUDOCODE
---------------------
span = int(n/2)
while span > 0 do:
for i = span .. n - 1 do:
   key =  num[i]
   j = i
   while j = span and num[j - span] > key do:
    num[j] = num[j - span]
    j = j - span
   num[j] = key
  span = int(span / 2.2)
****************************************************************************/

#include "iostream.h"
#include "conio.h"

void insertionSort(int num[],int N)
{
int i,j,key;
for(j = 1;j < N;j++) //From Second Element to Last
{
  key = num[j]; //Assign num[j] to key
   i = j - 1;
   while(i >= 0 && num[i] > key)
    {
     //Swap two elements
   num[i + 1] = num[i];
      i--;
      num[i + 1] = key;
    }
}
}

int main()
{
int num[50],N,i,j,span,key;
cout << "How many numbers? " ;
cin >> N;
cout << "\nEnter " << N << " Numbers\n";
for(i = 0;i < N;i++)
  cin >> num[i];

span = int(N/2);
while(span > 0)
  {
   for(i = span;i < N;i += span)
    {
     key = num[i];
     j = i;
     while(j >= span && num[j - span] > key)
      {
       num[j] = num[j - span];
       j = j - span;
      }

     num[j] = key;
    }
  span = int(span/2.2);
  }

//Now, the array of data is almost sorted
//So, using Insertion Sort as last step
insertionSort(num,N);

cout << endl;
for(int i = 0;i < N;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

Shell.cpp

2 comments:

Anonymous said...

nice ! post more codes !

Anonymous said...

how about sort strings using shell sort?

Post a Comment

Leave Feedback about this BLOG