Shell Sort

Shell Sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shell Sort is to allow exchange of far items. 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 sub-lists of every h’th element is sorted.

From the below animation it can be seen that Shell sort works fastest for nearly sorted array of elements. The time required to sort the elements increases in the order: few unique, reversed and then random.

What are random, nearly sorted, reversed and few unique elements?

  1. Random: {6, 9, 5, 8, 7, 4, 2, 1, 3}
    Here all the elements are arranged in a random fashion.
  2. Nearly sorted: {5, 6, 7, 8, 9, 1, 2, 3, 4}
    The array is nearly sorted. For example, the above array if divided into two, are sorted individually.
  3. Reversed: {9, 8, 7, 6, 5, 4, 3, 2, 1}
    The array elements are reverse sorted and we are supported to sort them in ascending order.
  4. Few Unique: {1, 1, 2, 9, 4, 3, 2, 5, 9, 6}
    The array contains duplicate entries.
Random Nearly Sorted Reversed Few Unique


Implementation

void shellSort(int arr[], int n)
{ 
    // Start with a big gap, then reduce the gap
    for (int gap = n/2; gap > 0; gap /= 2)
    { 
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is gap sorted 
        for (int i = gap; i < n; i += 1)         
        {   
        /* add a[i] to the elements that have been gap sorted, save a[i] in temp and make a hole at position i */             
            int temp = arr[i];               
         /* shift earlier gap-sorted elements up until the correct location for a[i] is found */             
            int j;                         
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    arr[j] = arr[j - gap];
         //  put temp (the original a[i]) in its correct location
            arr[j] = temp;
        }
    }
}

Analysis

A Shellsort’s worst-case performance using Hibbard’s increments is Θ(n 3/2). The average performance is thought to be about O(n5/4)

The exact complexity of this algorithm is still being debated. Experience shows that for mid-sized data (tens of thousands elements) the algorithm performs nearly as well if not better than the faster n log n sorts.


Auxiliary Space: O(1)
Sorting In Place: Yes
Stable: No

It is an unstable sort since it uses gap sequence. It is used to sort short subarrays and to prevent a pathological slowdown when the recursion depth exceeds a given limit. This principle is employed, for instance, in the bzip2 compressor.

Source: Wikipedia