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

Идея

Сортировка вставками медленная, потому что элемент за один сдвиг перемещается всего на одну позицию. Дональд Шелл (1959) предложил сначала сортировать далеко отстоящие элементы: упорядочить каждый h-й элемент (массив становится «h-отсортированным»), затем взять h поменьше и закончить при h = 1 — обычной сортировкой вставками, которая теперь работает быстро, потому что каждый элемент уже близко к своему месту.

Реализация использует последовательность шагов Кнута 1, 4, 13, 40, 121, … (h = 3h + 1), начиная с наибольшего шага меньше n/3.

Пример

Сортируем [9, 8, 3, 7, 5, 6, 4, 1, 2, 0] (n = 10, шаги 4 и 1).

Шаг 4 — четыре независимые сортировки вставками по позициям {0, 4, 8}, {1, 5, 9}, {2, 6}, {3, 7}:

Группа	До	После
0, 4, 8	9, 5, 2	2, 5, 9
1, 5, 9	8, 6, 0	0, 6, 8
2, 6	3, 4	3, 4
3, 7	7, 1	1, 7

Массив: 2, 0, 3, 1, 5, 6, 4, 7, 9, 8 — каждый элемент в нескольких позициях от своего места.

Шаг 1 — сортировка вставками заканчивает работу всего за 6 сдвигов (6 оставшихся инверсий): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

SHELL-SORT(A)
  h = 1
  while h < ⌊n / 3⌋
    h = 3h + 1
  while h ≥ 1
    for i = h to n − 1            // сортировка вставками с шагом h
      key = A[i]
      j = i
      while j ≥ h and A[j − h] > key
        A[j] = A[j − h]
        j = j − h
      A[j] = key
    h = (h − 1) / 3

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n log n)	≈ O(n^1.25)	O(n^1.5)	O(1)	нет	да

• Сложность зависит от последовательности шагов и до сих пор остаётся открытой задачей. Для последовательности Кнута доказан худший случай O(n^(3/2)) (Пратт, 1971); в среднем наблюдается около n^1.25.
• Исходная последовательность Шелла n/2, n/4, …, 1 хуже: O(n²) в худшем случае.
• Неустойчивая: длинные прыжки могут перенести элемент через равный.

Когда применять

Когда нужно что-то гораздо быстрее O(n²), но простое, без рекурсии и без дополнительной памяти — например, во встраиваемых системах. На больших массивах выигрывают алгоритмы O(n log n).

Использование

import { shellSort } from 'ts-ds';

const array = [9, 8, 3, 7, 5, 6, 4, 1, 2, 0];
shellSort(array);

Справочник API

Литература

• D. L. Shell. «A high-speed sorting procedure». Communications of the ACM 2(7), 1959.
• Кнут, Искусство программирования, т. 3, §5.2.1 «Метод Шелла».
• Седжвик, Алгоритмы, §2.1.