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

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

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

Алгоритм

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

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

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

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

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

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

Ссылки

Сортировки обменами

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

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

Comb sort

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