Shell sort

Shell sort is an unstable quadratic sorting algorithm, which can be seen as a generalization of insertion sort. Althrought is has an O(n^2) asymptotic complexity, it is the most efficient algorithm of this class.

Description

An ordinary insertion sort maintains a list of already sorted elements. Than it picks the element next to the list and places it at the correct position within the list. By iteratively repeating this procedure (starting with a list of one element) the array gets sorted in steps.

Shell sort operates analogously. The main difference is, that Shell sort uses so called diminishing increment. It means that in every step only elements at some distance are compared (for example the first with the fifth, second with the sixth...). This approach ensures that elements with high and low value are moved to the appropriate side of the array very quickly. In every iteration the gap between the compared elements is reduced. In the iteration step, the gap is set to one – the algorithm degrades to an ordinary insertion sort, which terminates very quickly, because now the array contains only few misplaced elements.

Optimal gap

The fundamental problem of Shell sort is to determine the optimal gap between compared elements. In the original algorithm Donald Shell proposed an initial gap of size n/2 ( is the size of the array), divided by in each step. Thich approach has one big disadvantage – elements at odd and even places are mutually compared only in the last step.

Other implementations used gap size $2^{k} - 1$ (Hibbard) with the worst case complexity $O(n^{3/2})$ , or $9 \\cdot 4^{i} - 9 \\cdot 2^{i}$ (Sedgewick) with complexity $O(n^{4/3})$ . The best performance is offered by a sequence by Marcin Ciura - 1, 4, 10, 23, 57, 132, 301, 701, 1750 every next gap size is generated by multiplying the previous size by 2.2 .

Visualization

Code

/**
 * Shell sort - sort with diminishing increment (descending)
 * @param array to be sorted
 * @return sorted array
 */
public static int[] shellSort(int[] array) {
    int gap = array.length / 2;
    while (gap > 0) {
        for (int i = 0; i < array.length - gap; i++) { //modified insertion sort
            int j = i + gap;
            int tmp = array[j];
            while (j >= gap && tmp > array[j - gap]) {
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = tmp;
        }
        if (gap == 2) { //change the gap size
            gap = 1;
        } else {
            gap /= 2.2;
        }
    }
    return array;
}

/**
 * Shell sort - sort with diminishing increment (descending)
 * @param array to be sorted
 * @param size array size
 * @return sorted array
 */
int * shellSort(int * array, int size) {
    int gap = size / 2;
    while (gap > 0) {
        for (int i = 0; i < size - gap; i++) { //modified insertion sort
            int j = i + gap;
            int tmp = array[j];
            while (j >= gap && tmp > array[j - gap]) {
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = tmp;
        }
        if (gap == 2) { //change the gap size
            gap = 1;
        } else {
            gap /= 2.2;
        }
    }
    return array;
}

/**
 * Shell sort - sort with diminishing increment (descending)
 * @param array to be sorted
 * @return sorted array
 */
 public static int[] ShellSort(int[] array)
 {
     int gap = array.Length / 2;
     while (gap > 0)
     { 
         for (int i = 0; i < array.Length - gap; i++) //modified insertion sort
         { 
             int j = i + gap;
             int tmp = array[j];
             while (j >= gap && tmp > array[j - gap])
             {
                 array[j] = array[j - gap];
                 j -= gap;
             }
             array[j] = tmp;
         }
         if (gap == 2) //change the gap size
         { 
             gap = 1;
         }
         else
         {
             gap = (int)(gap / 2.2);
         }
     }
     return array;
 }

Description

Optimal gap

Visualization

Code

Place for your banner