Shell Sort

1. Shell Sort Algorithm
2. Shell Sort Example
3. Shell Sort Algorithm Implementation
4. Shell Sort Algorithm Complexity

Shell sort is a highly efficient comparison-based sorting algorithm. It is seen as the generalization of the bubble sort algorithm or an optimized insertion sort algorithm. In the insertion sort algorithm, we move elements one position ahead. But in the case of shell sort, we move elements h positions ahead. It starts by sorting very far elements and gradually reduces the gap based on a sequence to sort the whole array. Some of the sequences used are:

Shell Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements. We will use the shell’s original sequence to sort the array.

Shell Sort Example

Suppose we have the array: (9, 8, 3, 7, 5, 6, 4, 1). We will sort it using the shell sort algorithm and use the shell’s original sequence to reduce the gap intervals.

• First Iteration

n/2 = 4 , elements lying at interval 4 are compared and swapped.

A[0] > A[4] → swapped, (5,8,3,7,9,6,4,1).

A[1] > A[5] → swapped, (5,6,3,7,9,8,4,1).

A[2] < A[6]

A[3] > A[7] → swapped, (5,6,3,1,9,8,4,7).

The array becomes: (5,6,3,1,9,8,4,7).

• Second Iteration

n/4 = 2 , element lying at interval 2 are compared and swapped.

A[0] > A[2] → swapped, (3,6,5,1,9,8,4,7).

A[1] > A[3] → swapped, (3,1,5,6,9,8,4,7).

A[0] < A[2] < A[4]

A[1] < A[3] < A[5]

A[2] > A[4] and A[4] > A[6] → swapped, (3,1,4,6,5,8,9,7).

A[1] < A[3] < A[5] but A[5] > A[7] → swapped, (3,1,4,6,5,7,9,8).

The array becomes: (3,1,4,6,5,7,9,8).

• Third Iteration

n/8 = 1 , element lying at interval 1 are compared and swapped.

A[0] > A[1] → swapped, (1,3,4,6,5,7,9,8).

A[0] .. A[2] → sorted

A[0] .. A[3] → sorted

A[0] .. A[3] → sorted but A[3] > A[4] → swapped, (1,3,4,5,6,7,9,8).

A[0] .. A[5] → sorted

A[0] .. A[6] → sorted

A[0] .. A[6] → sorted but A[6] > A[7] → swapped, (1, 3, 4, 5, 6, 7, 8, 9).

Shell Sort Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Shell Sort Algorithm Complexity

Time Complexity

• Average Case

The complexity depends on the sequence chosen for sorting. The time complexity is of the order of [Big Theta]: O(nlog(n)²).

• Worst Case

The worst-case time complexity for shell sort is always less than equal to O(n²). More precisely according to Poonen’s theorem, it is given by Θ(nlogn)²/(log log n)²) or Θ(nlog n)²/log log n) or Θ(n(log n)²) or something in between. The worst-case time complexity is [Big O]: less than equal to O(n²).

• Best Case

The best-case occurs when the array is already sorted and the comparisons required for each interval is the same as the size of the array. The best-case time complexity is [Big Omega]: O(nlogn).

Space Complexity

Space Complexity for the Shell sort algorithm is O(n) because no extra memory other than a temporary variable is required.