Shell Sort

- Does not sort entire array at once, it divide the array into noncontiguous segment,                                          which are separately sorted by using insertion sort.
- Once all of the segments are sorted, Shell sort redivides the array into less segments                                          and repeat the algorithm until at last that the number of segment equals 1, and the
segment is sorted.
 

SHELL SORT ANIMATION PAGE

STATIC SORT FOR SHELL SORT

PROGRAM WRITTEN IN C++ FOR BUBBLE SORT

#include<iostream.h>
#include<string.h>
#include<conio.h>

void shell( int A[], int n,int incrmnt[], int numinc);

main()
{
     int A[20],n,no,incrmnt[10],numinc=3;

     incrmnt[0]=3;
     incrmnt[1]=2;
     incrmnt[2]=1 ;

     cout << " Input n:  " ;
     cin >> n;
     cout << "\n Input number :  ";

     for(int i=0;i<n;i++)
     {     cin >>no;
            A[i]=no;
      }
 
      shell(A,n,incrmnt,numinc);

      return 0;
}
 

void shell( int A[], int n,int incrmnt[], int numinc)
{       int incr,j,k,span,y,l,iteration=0;

         for (incr=0; incr < numinc; incr++)
         {
              // span is the size of the increment

              span = incrmnt[incr];

              for( j=span; j<n;j++)
              {
                // Insert element A[j] into its proper position within its subfile

                    y = A[j];

                    for( k=j-span; k>=0 && y<A[k];k-=span)
                           A[k+span]=A[k];
                    A[k+span]=y;

               }
          } // end for
} // end shell