Program for Shell Sort in C

Shell short is an improved and efficient version of the insertion sort.

In this algorithm, we sort the pair of elements that are far apart by gap h.
 The process is repeated by reducing h until it becomes 1.

Shell Sort

Algorithm

Following is the algorithm for shell sort.

Step 1 − Initialize the value of h

Step 2 − Divide the list into smaller 
               sub-list of equal interval h

Step 3 − Sort these sub-lists using insertion sort


Step 4 − Repeat until the complete list is sorted


Program for Shell Sort in C

#include<stdio.h>

void sort(int a[],int n)
{
int gap,i,j,temp;

for(gap=n/2;gap>0;gap/=2)
{
for(i=gap;i<n;i+=1)
{
temp=a[i];

for(j=i;j>=gap&&a[j-gap]>temp;j-=gap)

     a[j]=a[j-gap];

  a[j]=temp;

}

}

}

int main()
{
int a[20],i,n;

printf("Enter number of elements:");

scanf("%d",&n);

printf("Enter array elements:\n");

for(i=0;i<n;++i)
{
scanf("%d",&a[i]);
} sort(a,n);

printf("\nArray after shell sort:\n");

for(i=0;i<n;++i)
printf("%d ",a[i]);

    return 0;
}


Output

Enter number of elements:5
Enter array elements:
56 7 2 9 12

Array after shell sort:
2 7 9 12 56