Сортировка Шелла (Shell sort)

Сортировка Шелла - это усовершенствованная версия сортировки вставками, которая позволяет уменьшить количество сравнений и перемещений элементов за счет использования промежуточных шагов.

Алгоритм

Алгоритм сортировки Шелла работает следующим образом:

1. Выбор начального значения шага, обычно равного половине длины массива.
2. Выполнение сортировки вставками для элементов, находящихся на расстоянии шага друг от друга.
3. Постепенное уменьшение шага и повторение процесса, пока шаг не станет равным 1.
4. На последнем шаге алгоритм выполняется как обычная сортировка вставками.

Анализ сложности

• Временная сложность сортировки Шелла: Зависит от выбора шагов. В худшем случае может достигать $O(n^2)$, но обычно работает значительно быстрее.
• Пространственная сложность сортировки Шелла: $O(1)$, так как сортировка выполняется на месте.

Реализация

Приведём примеры реализации сортировки Шелла:

Python

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

C++

#include <vector>

void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

Java

public void shellSort(int[] arr) {
    int n = arr.length;

    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

Заключение

Сортировка Шелла является более эффективной альтернативой традиционной сортировке вставками, особенно для больших массивов, благодаря использованию шагов, которые позволяют элементам быстрее достигать своего конечного положения в отсортированном массиве.