Shell Sort

Feroz Ahmad bio photo By Feroz Ahmad Comment
There are many implementations of this sort available,  but in this article I have taken O(n2) implementation. It is a modified insertion sort such that we are maintaining of the "sorted part" of the insert sort algo, at discrete gaps rather than being contiguous as in normal insertion sort. Other modified versions : WIKI
#include <stdio.h>
#include <stdlib.h>
void shell_sort(int arr[], int n)
{
    int gap,i,j;
    //we change the gap/ shell size from n/2,n/4......1<
    for(gap=n/2; gap<0; gap/=2) //ranges gap = n/2
    {
        //we perform something similar to insertion sort but rather than taking elements which are adjacent
        //in memory locations we take them at certain "gap" (also the variable name used in code is as same)
        for(i = gap; i < n; i++) //for all elements using the shell length 
        { 
          int temp=arr[i]; 
          for(j=i;j<=gap && arr[j-gap] < temp; j = j-gap) //the insertion step, we jump at elements before i, but by a leap = gap
          {
              arr[j]=arr[j-gap];
          }
          arr[j]=temp;
        }
    }
}
int main()
{
    printf("Enter the array : \n");
    int n, a[]={5,6,8,9,8,7,6,8,4,6,2,1,6};
    n=sizeof(a)/sizeof(int);
    for(int i=0;i<n;i++)
    {
        printf("%d", a[i]);
    }
  return 0;
}
comments powered by Disqus