Сортировка расчёской :: Comb sort

Модификация пузырьковой сортировки с весьма высокой временной сложностью. На массивах до нескольких тысяч элементов показывает скорость выше чем у быстрой сортировки.

Аналогичная идея используется и для трансформации сортировки простыми вставками в сортировку Шелла.

Сортировка расчёской

Алгоритм

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

В пузырьковой сортировке при каждом прогоне по массиву сравниваются соседние элементы. Здесь же сравниваются элементы, между которыми некоторое фиксированное расстояние. При каждом следующем прохождении расстояние уменьшается, пока не достигнет минимальной величины.

Уменьшающееся расстояние между сравниваемыми элементами рассчитывается с помощью специальной величины, называемой фактором уменьшения. Длина массива делится на этот фактор, это и есть разрыв между индексами. После каждого прохода расстояние делится на фактор уменьшения и таким образом получается новое значение. В конце концов оно сужается до минимального значения — единицы, и массив просто досортировывается обычным «пузырьком».

В результате практических тестов и теоретических исследований оптимальное значение для фактора уменьшения определено следующее:

Фактор уменьшения

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

Название Пузырьковая сортировка (Bubble sort)
Автор Влодзимеж Добосиевич (Włodzimierz Dobosiewicz),
Стивен Лейси (Stephen Lacey), Ричард Бокс (Richard Box)
Год 1980; 1991
Класс Сортировки обменами
Устойчивость Да
Сравнения Да
Сложность по времени Худшая Ω(n2)
Средняя Ω(n2/2p)
Лучшая O(n)
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

Хабрахабр: Пузырьковая сортировка и все-все-все

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

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