In this tutorial, you'll find out how the shell sort algorithm works. You'll also find working samples of shell sort in C, C ++, Java, and Python.

Shell sort is an algorithm that first sorts of items that are far aside from one another and successively reduces the interval between items to be sorted. it's a generalized version of insertion sort.

In shell sorting, items at a selected interval are sorted. The interval between elements is gradually reduced counting on the sequence used. The performance of the shell sort depends on the sort of sequence used for a given input array.

Some of the optimal sequences used are:

•  Shell's original sequence: N / 2, N / 4,…, 1
•  Knuth increments: 1, 4, 13,…, (3k - 1) / 2
•  Sedgewick increments: 1, 8, 23, 77, 281, 1073, 4193, 16577 ... 4d + 1 + 3 2d + 1
•  Hibbard increments: 1, 3, 7, 15, 31, 63, 127, 255, 511 ...
•  Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65, ...
•  Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81 ....

How does the Shell sort Algorithm work?

•  Suppose we'd like to sort the subsequent table.

shell sort sequence

 

• We use the first shell sequence (N / 2, N / 4, ... 1) as intervals in our algorithm.

In the first loop, if the dimensions of the array is N = 8 then the weather located at the interval of N / 2 = 4 is compared and exchanged if they're out of order.

•  The 0th element is compared to the 4th element.

•  If the 0th element is bigger than the 4th then, the 4th element is first stored within the variable temp, and therefore the 0th element (i.e. largest element) is stored within the 4th position, and therefore the stored element in temp is stored within the 0th position.

Shell Sort algorithm

This process continues for all remaining items.

rearrange the element in shell sort

In the second loop, an interval of N / 4 = 8/4 = 2 is taken and again the things at these intervals are sorted.

shell sort algorithm

You might be confused now.

shell sort in the data structure

The elements in the 4th and 2nd position are compared. the weather in the 2nd and 0th positions also are compared. All array elements at the present interval are compared.

• The same process continues for the remaining items.

shell sort in the data structure

• Finally, when the interval is N / 8 = 8/8 = 1, the array elements located at the interval of 1 are sorted. The table is now completely sorted.

 

shell sort in the data structure

Shell sort example in C

#include<stdio.h> 

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

// Print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
  int size = sizeof(data) / sizeof(data[0]);
  shellSort(data, size);
  printf("Sorted array: \n");
  printArray(data, size);
}

Time Complexity For Shell Sort Algorithm

Time complexity

•  Worst case complexity: but or adequate to O (n2)

 The worst case complexity for the shell sort is usually but or adequate to O (n2).

 consistent with Poonen's theorem, the worst-case complexity for shell sorting is Θ (Nlog N) 2 / (log log N) 2) or Θ (Nlog N) 2 / log log N) or Θ (N (log N) ) 2) or something in between.

•  Best case complexity: O (n * log n)

 When the array is already sorted, the entire number of comparisons for every interval (or increment) is adequate to the dimensions of the array.

•  Average complexity of cases: O (n * log n)

 it's located around O (n1,25).

The complexity depends on the chosen interval. The above complexities differ for the various increment sequences chosen. the simplest increment sequence is unknown.

• Space complexity:

The spatial complexity for the shell sort is O (1).

Shell sorting Algorithm applications

•  calling a stack is overloading. The uClibc library uses this type.
•  recursion exceeds a limit. The bzip2 compressor uses it.
•  Insertion sorting doesn't work correctly when nearby items are far apart. Sorting shells helps reduce the space between nearby items. Thus, there'll be fewer permutations to perform.