Shell sort

1.Shell sort

• 是insertion sort的改良, 又稱為增量遞減排序排序法 (diminishing increment sort), 謝耳排序法

• 將原本的list藉由"increment"來切成sub-list

  • 每個sub-list皆用insertion sort來排序

  • 逐漸降低Increment直到等於1

  • 利用前一次排序的成果來加快排序

• The cool thing is that since that since the list was almost sorted it's far easier to get to a fully sorted state with increment set to 1.

  • Shell sort的表現比Insertion sort好

2.Procedures

3.Example code (Java)

• Modified insertion sort

  • Insertion sort takes in a start index and an increment

  • All iterations through the list are based on the increment

  • Adjacent elements separated by an increment are compared

  • Break out of the inner loop if no element is swapped

public static void insertionSort(int[] listToSort, int startIndex, int increment) {
    for (int i = 0; i < listToSort.length; i = i + increment) {
        for (int j = Math.min(i + increment, listToSort.length - 1)
             j - increment >= 0;
             j = j - increment) {
            if (listToSort[j] < listToSort[j - increment]) {
                swap(listToSort, j, j - increment);
            } else {
                break;
            }
        }
        print(listToSort);
    }
}

• Shell sort

  • Picked an increment at random

  • Slowly reduce the increment

public static void shellSort(int[] listToSort){
    int increment = listToSort.length / 2;
    while (increment >= 1) {
        for (int startIndex = 0; startIndex < increment; startIndex++) {
            insertionSort(listToSort, startIndex, increment);
        }
        increment = increment / 2;
    }
}

4.Complexity

• Getting the exact complexity of Shell sort is hard because it depends on the increment values chosen

• It's also not clear what the best increment value is.

• The complexity of Shell sort is better than insertion sort as the final iteration sort with increment = 1 has to work with a nearly sorted list.

  • The complexity of Shell sort is somewhere between O(N) and O(N^2)

  • Different value of increments produce different complexities

• The algorithm is adaptive since it's based on insertion sort which is adaptive.

• It takes O(1) extra space, it sorts in space (No extra space)

  • 因為用原本的list儲存 (in-place 演算法)