Implementation of Shell Sort Algorithm in C

In this tutorial, we will write a C program to implement shell sort. Before that, you may go through the following topics in C.

• function in C
• for loop in C

Shell Sort Algorithm

Shell sort is an in-place comparison-based sorting algorithm and variation of Insertion sort. It is a better version of Insertion sort in comparison-based. It can compare the elements far apart whereas Insertion compares adjacent elements.

In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

---

Implementation of Shell Sort Algorithm in C

Question: C program to implement Shell sort using function.

// Shell Sort in C programming
#include <stdio.h>

//function prototype
void shellSort(int array[], int n);

int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  //calling sorting function
  shellSort(arr, n);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

// Shell sort
void shellSort(int arr[], int n)
{
  //Rearrange the array elements at n/2, n/4, ..., 1 intervals 
  for (int interval = n / 2; interval > 0; interval /= 2)
  {
    for (int i = interval; i < n; i += 1)
    {
      int temp = arr[i];
      int j;

      for (j = i; j >= interval && arr[j - interval] > temp; j -= interval)
        arr[j] = arr[j - interval];

      arr[j] = temp;
    }
  }
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
55
3
356
124
54
18

Array after sorting:
3 18 54 55 124 356

Time Complexity of Shell Sort:

• Best case:  0(nlogn)
• Average case:  0(n(logn)^2)
• Worst case:  0(n(logn)^2)

---