brief introduction

Shell's sort is Insertion sort One of them, also known as "reducing increment sort", is a more efficient version of the direct insertion sort algorithm. Hill sort is an unstable sort algorithm. This method was named after D.L.Shell in 1959. Excerpts from: Baidu Encyclopedia

Code

algorithm analysis

private static final void sort(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int sentinel = array[i];
        for (int j = i - gap; j >= 0; j -= gap) {
            if (array[j] > sentinel) {
                array[j + gap] = array[j];
                array[j] = sentinel;
            } else {
                break;
            }
        }
    }
}

// Execution sequencing
// [27, 12, 36, 12, 24, 68, 59, 91, 45]
sort(array, 5);
// [12, 12, 36, 27, 24, 45, 59, 91, 68]
sort(array, 3);
// [12, 12, 24, 27, 36, 45, 59, 68, 91]
sort(array, 1);

In fact, the sort function in the code is essentially an insertion sort, but the traversal increment of the sequence is changed from 1 to the specified variable (gap). When the increment is not 1, the insertion sort changes the sequence of the sublist with the interval of the specified increment (grouping sort). Therefore, after the completion of sorting, the sequence is not completely ordered. Until the increment is 1, the sequence will not become after the completion of sorting Overall order (after the actual direct execution of the sorting with increment of 1, the sequence can be ordered directly, but this sorting is a simple insertion sorting). Although the sorting with increment of not 1 can not make the sequence overall order, it can be converted into basic order. When the last step of the insertion sorting (with increment of 1), the number of element moves will be reduced. There is no final conclusion about the step value in Hill's sorting and it can't prove an optimal value. Here we simply use the method of reducing the list length by half

Java version

private static final void sort(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int sentinel = array[i];
        for (int j = i - gap; j >= 0; j -= gap) {
            if (array[j] > sentinel) {
                array[j + gap] = array[j];
                array[j] = sentinel;
            } else {
                break;
            }
        }
    }
}

private static final void sort(int[] array) {
    // Select the sorting increment by halving the list length. When the increment is 1, the sorting ends
    for (int gap = array.length / 2; gap > 0; gap /= 2) {
        sort(array, gap);
    }
}

Python version

def shell_sort_once(lst, gap):
    for i in range(gap, len(lst)):
        key = lst[i]
        j = i - gap
        while j >= 0:
            if lst[j] > key:
                lst[j + gap], lst[j] = lst[j], key
            else:
                break
            j -= gap

gap = len(lst) // 2
while gap > 0:
    shell_sort_once(lst, gap)
    gap //= 2

epilogue

Hill sort is a kind of unstable sort (related to incremental selection). Its essence is still insertion sort, which is generally more efficient than insertion sort (related to the sequence itself, for example, the sequence itself is an ordered sequence, while Hill sort is not as efficient as insertion sort)

PS: when I read other Hill sorting codes, I always get confused by their N-layer loop. Later, when I understand that the internal loop is actually just the insertion sort, and the external loop is an incremental iteration cycle, I can figure it out. When I write, I usually use functions to pull out the single insertion sort, and the code will be easier to read and understand.