Easy Tutorial
❮ Es6 Symbol Docker Tricks ❯

1.4 Shell Sort

Category Algorithm

Shell sort, also known as the diminishing increment sort algorithm, is a more efficient improved version of insertion sort. However, shell sort is an unstable sorting algorithm.

The idea of shell sort is based on the following two properties of insertion sort:

The basic idea of shell sort is: first, divide the entire sequence of records to be sorted into several subsequences for direct insertion sort, and when the records in the entire sequence are "basically ordered," then perform direct insertion sort for all records.

1. Algorithm Steps

Select an increment sequence t1, t2, ..., tk, where ti > tj, tk = 1;

Sort the sequence in k passes according to the number of increments;

In each pass, according to the corresponding increment ti, divide the sequence to be sorted into several subsequences of length m, and perform direct insertion sort for each subsequence. When the increment factor is 1, the entire sequence is treated as a table, and the table length is the length of the entire sequence.

2. Animated Demonstration


Code Implementation

JavaScript

Example

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) { // Dynamically define the gap sequence
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

Python

Example

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
    return arr

Go

Example

func shellSort(arr []int) []int {
    length := len(arr)
    gap := 1
    for gap < length/3 {
        gap = gap*3 + 1
    }
    for gap > 0 {
        for i := gap; i < length; i++ {
            temp := arr[i]
            j := i - gap
            for j >= 0 && arr[j] > temp {
                arr[j+gap] = arr[j]
                j -= gap
            }
            arr[j+gap] = temp
        }
        gap = gap / 3
    }
    return arr
}

Java

Example

public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

PHP

Example

``` function shellSort($arr) { $len = count($arr); $temp = 0; $gap = 1; while($gap < $len / 3) { $gap = $gap * 3 + 1; } for ($gap; $gap > 0; $gap = floor($gap / 3)) { for ($i = $gap; $i < $len; $i++) { $temp = $arr[$i]; for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) { $arr[$j+$gap] = $arr[$j

WeChat Follow

❮ Es6 Symbol Docker Tricks ❯