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

Сортировка Шелла — это модифицированная сортировка простыми вставками.

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

Алгоритм

Сортировка Шелла примерно так же получается из сортировки вставками, как пузырьковая сортировка трансформируется в сортировку расчёской.

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

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

Сложность по времени

Известно, что при удачном раскладе этот способ сортирует за O(n). Но, в целом, сортировка работает существенно медленнее чем, к примеру быстрая сортировка или сортировка слиянием. Средняя временная сложность зависит от того, какую последовательность брать для циклических итераций.

Первоначально автор сортировки, Дональд Шелл, предложил ряд
[n/4], [n/2], [n/8], …, 1
который давал скорость O(n2).
В течении последующих 50 лет, многие исследователи (среди которых — легендарный Роберт Седжвик) подбирали различные зависимости, постепенно улучшая результат. На данный момент таковым является ряд, предложенный в 2001 году Марсином Сиурой:
701, 301, 132, 57, 23, 10, 4, 1.
Это — результат многочисленных тестов, до сих пор неизвестно, можно или нельзя его улучшить.

Характеристики алгоритма

Название Сортировка Шелла (Shell sort, Shellsort)
Автор Дональд Шелл
Год 1959
Класс Сортировки вставками
Устойчивость Нет
Сравнения Да
Сложность по времени Худшая Зависит от шага
Средняя
Лучшая O(n)
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

Хабрахабр: Глупая сортировка и некоторые другие, поумнее
Хабрахабр: И снова про сортировки: выбираем лучший алгоритм

Сортировка Шелла в Википедии
Shell sort on Wikipedia
Реализация на различных ЯП

One thought on “Сортировка Шелла :: Shell sort

  1. Pingback: Шелла

Добавить комментарий