Shell Sort Algorithm

In this article, we will discuss the shell sort algorithm. Shell sort is the generalization of insertion sort, which overcomes the drawbacks of insertion sort by comparing elements separated by a gap of several positions.

It is a sorting algorithm that is an extended version of insertion sort. Shell sort has improved the average time complexity of insertion sort. As similar to insertion sort, it is a comparison-based and in-place sorting algorithm. Shell sort is efficient for medium-sized data sets.

In insertion sort, at a time, elements can be moved ahead by one position only. To move an element to a far-away position, many movements are required that increase the algorithm’s execution time. But shell sort overcomes this drawback of insertion sort. It allows the movement and swapping of far-away elements as well.

This algorithm first sorts the elements that are far away from each other, then it subsequently reduces the gap between them. This gap is called as interval. This interval can be calculated by using the Knuth’s formula given below –

Now, let’s see the algorithm of shell sort.

Algorithm

The simple steps of achieving the shell sort are listed as follows –

  ShellSort(a, n) // ‘a’ is the given array, ‘n’ is the size of array  for (interval = n/2; interval > 0; interval /= 2)  for ( i = interval; i < n; i += 1)  temp = a[i];  for (j = i; j >= interval && a[j – interval] > temp; j -= interval)  a[j] = a[j – interval];  a[j] = temp;  End ShellSort  

Working of Shell sort Algorithm

Now, let’s see the working of the shell sort Algorithm.

To understand the working of the shell sort algorithm, let’s take an unsorted array. It will be easier to understand the shell sort via an example.

Let the elements of array are –

We will use the original sequence of shell sort, i.e., N/2, N/4,….,1 as the intervals.

In the first loop, n is equal to 8 (size of the array), so the elements are lying at the interval of 4 (n/2 = 4). Elements will be compared and swapped if they are not in order.

Here, in the first loop, the element at the 0^th position will be compared with the element at 4^th position. If the 0^th element is greater, it will be swapped with the element at 4^th position. Otherwise, it remains the same. This process will continue for the remaining elements.

At the interval of 4, the sublists are {33, 12}, {31, 17}, {40, 25}, {8, 42}.

Now, we have to compare the values in every sub-list. After comparing, we have to swap them if required in the original array. After comparing and swapping, the updated array will look as follows –

In the second loop, elements are lying at the interval of 2 (n/4 = 2), where n = 8.

Now, we are taking the interval of 2 to sort the rest of the array. With an interval of 2, two sublists will be generated – {12, 25, 33, 40}, and {17, 8, 31, 42}.

Now, we again have to compare the values in every sub-list. After comparing, we have to swap them if required in the original array. After comparing and swapping, the updated array will look as follows –

In the third loop, elements are lying at the interval of 1 (n/8 = 1), where n = 8. At last, we use the interval of value 1 to sort the rest of the array elements. In this step, shell sort uses insertion sort to sort the array elements.

Now, the array is sorted in ascending order.

Shell sort complexity

Now, let’s see the time complexity of Shell sort in the best case, average case, and worst case. We will also see the space complexity of the Shell sort.

1. Time Complexity

Case	Time Complexity
Best Case	O(n*logn)
Average Case	O(n*log(n)²)
Worst Case	O(n²)

Best Case Complexity – It occurs when there is no sorting required, i.e., the array is already sorted. The best-case time complexity of Shell sort is O(n*logn).
Average Case Complexity – It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of Shell sort is O(n*logn).
Worst Case Complexity – It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of Shell sort is O(n²).

2. Space Complexity

Space Complexity	O(1)
Stable	NO

The space complexity of Shell sort is O(1).

Implementation of Shell sort

Now, let’s see the programs of Shell sort in different programming languages.

Program: Write a program to implement Shell sort in C language.

  #include <stdio.h>    /* function to implement shellSort */  int shell(int a[], 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)  {  /* store a[i] to the variable temp and make the ith position empty */  int temp = a[i];  int j;  for (j = i; j >= interval && a[j – interval] > temp; j -= interval)  a[j] = a[j – interval];    // put temp (the original a[i]) in its correct position  a[j] = temp;  }  }  return 0;  }  void printArr(int a[], int n) /* function to print the array elements */  {  int i;  for (i = 0; i < n; i++)  printf(“%d “, a[i]);  }    int main()  {  int a[] = { 33, 31, 40, 8, 12, 17, 25, 42 };  int n = sizeof(a) / sizeof(a[0]);      printf(“Before sorting array elements are – n”);      printArr(a, n);      shell(a, n);      printf(“nAfter applying shell sort, the array elements are – n”);        printArr(a, n);  return 0;  }  

Output

After the execution of above code, the output will be –

Program: Write a program to implement Shell sort in C++.

  #include <iostream>  using namespace std;  /* function to implement shellSort */  int shell(int a[], 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)  {  /* store a[i] to the variable temp and make the ith position empty */  int temp = a[i];  int j;  for (j = i; j >= interval && a[j – interval] > temp; j -= interval)  a[j] = a[j – interval];    // put temp (the original a[i]) in its correct position  a[j] = temp;  }  }  return 0;  }  void printArr(int a[], int n) /* function to print the array elements */  {  int i;  for (i = 0; i < n; i++)  cout<<a[i]<<” “;  }      int main()  {  int a[] = { 32, 30, 39, 7, 11, 16, 24, 41 };  int n = sizeof(a) / sizeof(a[0]);      cout<<“Before sorting array elements are – n”;      printArr(a, n);      shell(a, n);      cout<<“nAfter applying shell sort, the array elements are – n”;        printArr(a, n);  return 0;  }  

Output

After the execution of the above code, the output will be –

Program: Write a program to implement Shell sort in C#.

  using System;  class ShellSort {  /* function to implement shellSort */  static void shell(int[] a, 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)  {  /* store a[i] to the variable temp and make the ith position empty */  int temp = a[i];  int j;  for (j = i; j >= interval && a[j – interval] > temp; j -= interval)  a[j] = a[j – interval];    /* put temp (the original a[i]) in its correct position */  a[j] = temp;  }  }  }  static void printArr(int[] a, int n) /* function to print the array elements */  {  int i;  for (i = 0; i < n; i++)  Console.Write(a[i] + ” “);  }  static void Main()   {  int[] a = { 31, 29, 38, 6, 10, 15, 23, 40 };  int n = a.Length;      Console.Write(“Before sorting array elements are – n”);      printArr(a, n);      shell(a, n);      Console.Write(“nAfter applying shell sort, the array elements are – n”);        printArr(a, n);  }     }  

Output

After the execution of the above code, the output will be –

Program: Write a program to implement Shell sort in Java.

  class ShellSort {  /* function to implement shellSort */  static void shell(int a[], 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)  {  /* store a[i] to the variable temp and make     the ith position empty */  int temp = a[i];  int j;  for (j = i; j >= interval && a[j – interval] >   temp; j -= interval)  a[j] = a[j – interval];    /* put temp (the original a[i]) in its correct   position */  a[j] = temp;  }  }  }  static void printArr(int a[], int n) /* function to print the array elements */  {  int i;  for (i = 0; i < n; i++)  System.out.print(a[i] + ” “);  }  public static void main(String args[])   {  int a[] = { 30, 28, 37, 5, 9, 14, 22, 39 };  int n = a.length;      System.out.print(“Before sorting array elements are – n”);      printArr(a, n);      shell(a, n);      System.out.print(“nAfter applying shell sort, the array elements are – n”);        printArr(a, n);  }      }  

Output

After the execution of the above code, the output will be –

So, that’s all about the article. Hope the article will be helpful and informative to you.

Next TopicBitonic Sort

Shell Sort

Shell Sort Algorithm

Algorithm

Working of Shell sort Algorithm

Shell sort complexity

1. Time Complexity

2. Space Complexity

Implementation of Shell sort

Priority Queue using Linked list

Bitmap Indexing

You may also like