Сортировка Шелла

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

Как работает Сортировка Шелла

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

Шаги алгоритма:

1. Выбор интервала: Начинаем с интервала, равного половине длины массива.
2. Сортировка подмассивов: Выполняем сортировку вставками для элементов, разделённых выбранным интервалом.
3. Уменьшение интервала: Интервал уменьшается, и процесс повторяется.
4. Финальная сортировка: Когда интервал становится равным 1, массив считается отсортированным.

Сложность алгоритма

Сложность Сортировки Шелла зависит от выбора интервалов и может варьироваться от O(nlogn) до O(n^2)в худшем случае.

Применение

Сортировка Шелла применяется для средних по размеру массивов и может использоваться как предварительная сортировка перед применением других алгоритмов.

Пример сортировки

Представим массив [13, 14, 94, 33, 82, 25]. После первого прохода с интервалом в 3 элемента, массив может выглядеть так: [13, 14, 25, 33, 82, 94]. После уменьшения интервала до 1, массив будет полностью отсортирован.

Реализация на C++

void shellSort(int* arr, int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i++) {
            int j;
            for (j = i; j >= interval && arr[j - interval] > arr[j]; j -= interval) {
                swap(arr[j], arr[j - interval]);
            }
        }
    } 
}

Сравнение различных алгоритмов сортировки

Время работы различных методов