Shell Sort

The shell sort is based on the insertion sort. The given list of elements is broken down in a few smaller lists. After this, the insertion sort is applied on such smaller lists. These smaller lists are again recombined. Another partition is made and the procedure is repeated. The breaking down of the list into smaller lists is by selecting elements at a specific location.

Algorithm for Shell Sort

shell sort implementation

#include <stdio.h>
#define MAX 20

int main()
{
  int arr[MAX], i,j,k,n,incr;
  printf("Enter the number of elements : ");
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Enter element %d : ",i+1);
    scanf("%d",&arr[i]);
  }
  printf("Unsorted list is :\n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\nEnter maximum increment (odd value) : ");
  scanf("%d",&incr);

  /*Shell sort*/
  while(incr>=1)
  {
    for(j=incr;j<n;j++)
    {
      k=arr[j];
      for(i = j-incr; i >= 0 && k < arr[i]; i = i-incr)
        arr[i+incr]=arr[i];
      arr[i+incr]=k;
    }
    printf("Increment=%d \n",incr);
    for (i = 0; i < n; i++)
      printf("%d ", arr[i]);
    printf("\n");
    incr=incr-2; /*Decrease the increment*/
  } //End of while

  printf("Sorted list is :\n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
        return 0;
}