Сортировка Шелла :: 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)

Ссылки

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

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

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

Shell sort

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