Shell Sort

Definition

Shell Sort, a sort named after its inventor, Donald Shell, is a sort that is based on Insertion Sort. Shell sort works as follows: it "places" all of the values into a table, and sorts each column using insertion sort. It then sorts it again with a smaller number of columns, and continues with smaller numbers of columns until there is only one column (Shell sort does not actually place the values into a table). It has a runtime of O(n2), which can be improved to O(nlogn).

Detailed Explanation

Shell Sort is based on two assumptions of insertion sort. Insertion sort is only efficient if the array is sorted, and it is inefficient because it can only move values one spot at a time. Shell sort improves on Insertion sort in the following ways. First, it can move values in giant steps. Small values that are located towards the end of the array are moved to the beginning with very few moves. In this way, values are moved toward a general area where they are expected to be, rather than the exact position in which they will stay. Insertion sort is efficient for the columns because it is originally starting with few values being compared, and later, the values are mostly sorted, in which insertion sort is efficient. When using Insertion Sort, instead of comparing values that are next to each other, it compares values that is n values away, which is called the increment.

Algorithm

  1. The increment is set as half the length of the array.
  2. Each "Column" is sorted using Insertion Sort.
    1. Compares values of index n and n + increment, and sorts them.
    2. Does this for all values that are in this "column", that have an index of n + y * increment.
    3. Sorts each "column" the same way, using n + 1 instead of n, and then n + 2…
  3. Sets the increment as the rounded integer of increment divided by 2.2 (the mystery of this 2.2 number is a little complex).
  4. Returns to step 2, unless the increment is less than one.

Code

public static void shellSort(int[] a) {
            for (int increment = a.length / 2; increment > 0;
                  increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
        //REMEMBER: the last part of the for loop works as follows.
        //increment =
        //if increment equals 2, then it sets increment as one
        //else it sets it as an int that is rounded, increment divided by 2.2
                for (int i = increment; i < a.length; i++) {
                    int toSort = a[i];
                    int scanBack;
                    for (scanBack = i; scanBack >= increment && a[scanBack - increment] > toSort; 
                               scanBack -= increment){
                        a[scanBack] = a[scanBack - increment];
 
                    }
                    a[scanBack] = toSort;
                }
            }
        }

Runtime

The runtime of Shell sort depends on the number you divide the increment by. Donald Shell originally divided the increment by 2, which gave it a runtime of O(n2). It can be improved to O(nlogn) by dividing by 2.2.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License