Shell Sort §

Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of entries that are far apart, to produce partially sorted arrays that can be efficiently sorted, eventually by insertion sort.

The idea is for item i in an array, instead of comparing all the items before i to correctly put i in position (that is what insertion sort does), shell sort only compares and sorts items in gap h. h is the number in a sequence. Some of the optimal sequences used are:

Shell’s original sequence

N/2 , N/4 , …, 1

Knuth’s increments

1, 4, 13, …, (3k – 1) / 2

Shell Sort Knuth Increments

Sedgewick’s increments

1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+3·2j+1

In each pass we keep reducing the value of gap till we reach the last pass when gap is 1

In the last pass shell sort is like the insertion sort

Implementation §

public class Shell {
  private Shell() {
  }
 
  public static void sort(Comparable[] a) {
    int n = a.length;
    // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
    int h = 1;
    while (h < n / 3)
      h = 3 * h + 1;
    while (h >= 1) {
      // h-sort the array
      for (int i = h; i < n; i++) {
        for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
          exch(a, j, j - h);
        }
      }
      assert isHsorted(a, h);
      h /= 3;
    }
    assert isSorted(a);
  }
 
  private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
  }
 
  // exchange a[i] and a[j]
  private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
  }
 
  private static boolean isSorted(Comparable[] a) {
    for (int i = 1; i < a.length; i++)
      if (less(a[i], a[i - 1]))
        return false;
    return true;
  }
 
  private static boolean isHsorted(Comparable[] a, int h) {
    for (int i = h; i < a.length; i++)
      if (less(a[i], a[i - h]))
        return false;
    return true;
  }
}

def shellSort(array, n):
    # Rearrange elements at each n/2, n/4, n/8, ... intervals
    interval = n // 2
    while interval > 0:
        for i in range(interval, n):
            temp = array[i]
            j = i
            while j >= interval and array[j - interval] > temp:
                array[j] = array[j - interval]
                j -= interval
            array[j] = temp
        interval //= 2
 
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print(data)

Complexity §

Stability: No Space Complexity: O(1)

Time Complexity §

• Worst Case Complexity Worst case complexity for shell sort is always less than or equal to O(n^2).

• Best Case Complexity When the array is already sorted, the total number of comparisons for each interval (or increment) is equal to the size of the array, hence O(n*log n)

• Average Case Complexity: O(n*log n)

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

Reference §

https://www.programiz.com/dsa/shell-sort https://algs4.cs.princeton.edu/21elementary/ https://www.youtube.com/watch?v=g06hNBhoS1k&ab_channel=udiprod Watch this youtube video first, the explanation is great.