Shell sorting was first introduced by Donald Shell.

It compares the element in the list that lies far apart for exchanging . The execution time is dependent on the gap it uses.

Algorithm for Shell Sort

step.1:
Set up a inc number. inc number is set according to given elements in the list.

step.2:
mark each elements which is comes in inc element.
For example, if list contains 10 elements then and we assume inc is 3 then, marking of elements such as next marking element, add last element +3 to get next element and so on. Then marking element would be 1st element, 4th element(add 3), 7th element(add 3), 10th element.

89  46  99  12  33  14  69  41  33  28

1    2    3    4    5    6   7    8   9   10 [index number]

step.3:
sort marking elements such as smallest to greater is set as left to right and not change remain element.
For example, we apply this step in above example:

12  46  99  28  33  14  69  41  33  89

step.4:
reduce inc number to one i.e. if inc number is earlier is 3 then now it would be 3-1 = 2.

step.5:
Repeat step 2,3 and 4 till all the elements not sorted.

Program for Shell Sort

#include<stdio.h>
#include<conio.h>
int main()
{
 int arr[30];
 int i,j,k,tmp,num;
 printf("Enter total no. of elements : ");
 scanf("%d", &num);
 for(k=0; k<num; k++)
 {
   printf("\nEnter %d number : ",k+1);
   scanf("%d",&arr[k]);
 }
 for(i=num/2; i>0; i=i/2)
 {
   for(j=i; j<num; j++)
   {
     for(k=j-i; k>=0; k=k-i)
     {
        if(arr[k+i]>=arr[k])
            break;
        else
        {
            tmp=arr[k];
            arr[k]=arr[k+i];
            arr[k+i]=tmp;
        }
     }
   }
 }
 printf("\t**** Shell Sorting ****\n");
 for(k=0; k<num; k++)
     printf("%d\t",arr[k]);
 getch();
 return 0;
}