Shell sort is quite similar to that of insertion sort with the only difference that in shell sort, higher values of k are considered. Whereas insertion sort assumes k to be 1. If k=4, then every 4th element is compared, if it is 3 then every 3rd element is compared. Thus k=m means every mth element gets compared with each other and is swapped.
The value of k is decremented after each scan. The file is sorted, when k becomes 1 and swapping is performed for k = 1. The difference in original and decremented value(i.e. difference in k) may be generated using a hash function, which returns the number of decrements in k. say k=4, then k=2 and finally k=1. k=3 is skipped. or (k=8, k=4, k=2, k=1) or (k=4, k=3, k=2, k=1).
If k is taken as 1 only, then it is no more shell sort, it becomes insertion sort.
/*Program to implement Shell Sort*/
#define MAX 5
void shellsort(int x,int n,int incrmnts,int numinc)
for(k=j-span;k>=0 && y<x[k]; k-=span)
A hash function may be defined as follows:
Let n be the size of the array (total number of elements).
Then begin from (n-3) upto 1.
Example: Let there are 8 elements, then n=8
increments array will hold 5,3,1 for (n-3), (n-5), (n-7) respectively.
and ct=3, where ct is numinc.
int hash(int arr,int n)
int arr[MAX],i,incrmnts[MAX], total_incr;
total_incr = hash(incrmnts,MAX);
printf(“Sorted array is: “);