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

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

Алгоритм

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

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

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

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

Известно, что при удачном раскладе этот способ сортирует за O(n). Но, в целом, сортировка работает существенно медленнее чем, к примеру быстрая сортировка или сортировка слиянием. Средняя временная сложность зависит от того, какую последовательность брать для циклических итераций.Первоначально автор сортировки, Дональд Шелл, предложил ряд[n/4], [n/2], [n/8], ..., который давал скорость O(n2).

В течении последующих 50 лет, многие исследователи (среди которых - легендарный Роберт Седжвик) подбирали различные зависимости, постепенно улучшая результат. На данный момент таковым является ряд, предложенный в 2001 году Марсином Сиурой:701, 301, 132, 57, 23, 10, 4, 1.

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

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

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

Ссылки

Сортировки вставками

Глупая сортировка и некоторые другие, поумнее

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

Shell sort

Реализация на различных ЯП