How to Implement Shell Sort in C Programming?

Shell Sort (aka shellsort) can be thought as an improvement over insertion sort. To understand shell sort, we have to recall how insertion sort works. In insertion sort at any moment, the whole array is sub-divided in two sections, one is sorted and another is not. One element is picked from the unsorted section and compares with the elements of sorted section one by one to get the right position for that element. We may need to compare with all elements of the sorted section to get the right position of the new element. This might happen for many or most of the elements. To improve this situation, in shell sort the insertion sort is done with the far apart elements first. In this process, some out-of-place elements will come to their right locations without needing too many comparisons. Then the gap between the elements, insertion sort is applied with, is reduced gradually. The algorithm stops after applying the insertion sort with gap 1.

Shell Sort Implementation in C

#include <stdio.h>

void shellsort(int *arr, int n){

  int tmp, gap, i, j;

  for (gap = n/2; gap > 0; gap /= 2)
  {
    for(i = gap; i < n; i++)
    {
      tmp = arr[i];
      for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)
      {
        arr[j] = arr[j - gap];
      }
      arr[j] = tmp;
    }
  }
}

void main()
{
  int arr[] = {54, 66, 31, 10, 4, 77, 32, 1, 56};
  int i = 0;

  printf("Array before sorting: ");
  for (i = 0; i < (sizeof(arr)/sizeof(int)); i++) printf(" %d", arr[i]);
  printf("\n");

  shellsort(arr, sizeof(arr)/sizeof(int));
  printf("Array after sorting: ");
  for (i = 0; i < (sizeof(arr)/sizeof(int)); i++) printf(" %d", arr[i]);
  printf("\n");
}

 

Performance of Shell Sort

Running time of shell sort is still a subject of study but in most cases it is O(N₂). Its performance is heavily dependent on the selection of gaps. But in most cases, the actual number of comparisons required is much less than the insertion sort.
The diagram below shows an experimental result how shell sort performs with respect to insertion sort with the increase of number of elements. Randomly ordered arrays were used for this experiment.

From the graph, we can see how performance improved significantly if we sort the far apart elements first then reduce the gap gradually till 1 than to apply insertion with gap 1.

Note: Similar concept can be applied on top of bubble sort also. We can apply bubble sort on far apart elements, then gradually reduce the gap to 1. This sort is also called shell sort.

If you also want to contribute, click here.