Сортировка Шелла :: 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) | |
Сортировка Шелла
Реализация на различных ЯП