**Shell Sort: **

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 4^{th} element is compared, if it is 3 then every 3^{rd} element is compared. Thus k=m means every m^{th} 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.

**Example:**

/*Program to implement Shell Sort*/

#include <stdio.h>

#include <conio.h>

#define MAX 5

void shellsort(int x[],int n,int incrmnts[],int numinc)

{

int incr,j,k,span,y;

for(incr=0;incr<numinc;incr++)

{

span=incrmnts[incr];

for(j=span;j<n;j++)

{

y=x[j];

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

x[k+span]=x[k];

x[k+span]=y;

}

}

}

/*

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 i,j=0,ct=0;

for(i=3;(n-i)>0;i+=2)

{

arr[j++]=n-i;

ct++;

}

if(arr[j-1]!=1)

{arr[j]=1;

ct++;

}

return ct;

}

void main()

{

int arr[MAX],i,incrmnts[MAX], total_incr;

for(i=0;i<MAX;i++)

{

incrmnts[i]=0;

printf(“Enter value?”);

scanf(“%d”,&arr[i]);

}

total_incr = hash(incrmnts,MAX);

shellsort(arr,MAX,incrmnts,total_incr);

printf(“Sorted array is: “);

for(i=0;i<MAX;i++)

{

printf(“%d\t”,arr[i]);

}

getch();

}