Сортировка расчёской :: Comb sort
Модификация пузырьковой сортировки с весьма высокой временной сложностью. На массивах до нескольких тысяч элементов показывает скорость выше чем у быстрой сортировки. Аналогичная идея используется и для трансформации сортировки простыми вставками в сортировку Шелла.
Алгоритм
Производятся неоднократные прогоны по массиву, при которых сравниваются пары элементов. Если они неотсортированы друг относительно друга - то производится обмен. В результате крупные элементы мигрируют в конец массива, а небольшие по значению - в начало.
В пузырьковой сортировке при каждом прогоне по массиву сравниваются соседние элементы. Здесь же сравниваются элементы, между которыми некоторое фиксированное расстояние. При каждом следующем прохождении расстояние уменьшается, пока не достигнет минимальной величины.
Уменьшающееся расстояние между сравниваемыми элементами рассчитывается с помощью специальной величины, называемой фактором уменьшения. Длина массива делится на этот фактор, это и есть разрыв между индексами. После каждого прохода расстояние делится на фактор уменьшения и таким образом получается новое значение. В конце концов оно сужается до минимального значения - единицы, и массив просто досортировывается обычным "пузырьком".
В результате практических тестов и теоретических исследований оптимальное значение для фактора уменьшения определено следующее:
Характеристики алгоритма
| Название | Пузырьковая сортировка (Bubble sort) | |
|---|---|---|
| Автор | Влодзимеж Добосиевич (Włodzimierz Dobosiewicz),Стивен Лейси (Stephen Lacey), Ричард Бокс (Richard Box) | |
| Год | 1980; 1991 | |
| Класс | Сортировки обменами | |
| Устойчивость | Да | |
| Сравнения | Да | |
| Сложность по времени | Худшая | Ω(n2) |
| Средняя | Ω(n2/2p) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Сортировка расчёской
Реализация на различных ЯП