Как реализовать алгоритм сортировки Шелла?

@ransom_homenick 

Алгоритм сортировки Шелла в основе использует идею сортировки вставками, но вместо того, чтобы сравнивать и перемещать соседние элементы, он сравнивает и перемещает элементы на определенное расстояние друг от друга.

Вот пример реализации алгоритма сортировки Шелла на языке Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # Начальное значение расстояния

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp

        gap //= 2  # Уменьшаем расстояние вдвое

    return arr

Для сортировки массива arr, алгоритм начинает с большого расстояния между сравниваемыми элементами (размер массива деленный пополам), а затем последовательно уменьшает это расстояние до 1. На каждом шаге алгоритм обрабатывает подмассивы элементов, находящихся на указанном расстоянии друг от друга, сортировкой вставками.

Алгоритм продолжает уменьшать расстояние вдвое, пока не достигнет значения 1, что является обычной сортировкой вставками.