2.2.1.11 — bubble sort, применяющий тот же трюк с gap, что и shell sort2.2.1.11 — bubble sort applying the same gap trick as shell sort
Главная слабость bubble sort — "черепахи": маленькие значения у правого конца массива, которым нужно пройти весь путь влево по одной позиции за раз. Comb sort устраняет именно эту проблему тем же способом, что shell sort устранил её для insertion sort — сравнивать элементы не с соседом, а с элементом на расстоянии gap, постепенно уменьшая gap до 1.Bubble sort's main weakness is "turtles": small values near the array's right end that need to travel the whole way left one position at a time. Comb sort fixes exactly this problem the same way shell sort fixed it for insertion sort — compare an element not with its neighbor but with one gap positions away, gradually shrinking the gap down to 1.
Изначально gap = n. На каждом проходе gap уменьшается делением на shrink-фактор (эмпирически лучшее значение — 1.3, взято из оригинальной статьи Бокса и Лейси 1990 года), и по всему массиву сравниваются пары (i, i+gap), меняясь местами при нарушении порядка. Когда gap становится равным 1, алгоритм превращается в обычный bubble sort — но к этому моменту большинство "дальних" инверсий уже устранено широкими gap-проходами, так что финальные проходы с gap=1 обычно требуют совсем немного перестановок. Цикл продолжается, пока либо gap не станет равным 1 и не пройдёт проход без перестановок.Initially gap = n. Each pass shrinks gap by dividing by a shrink factor (empirically best around 1.3, from Box and Lacey's original 1990 paper), and pairs (i, i+gap) across the whole array are compared, swapping on disorder. Once gap reaches 1, the algorithm becomes ordinary bubble sort — but by then most "long-range" inversions have already been removed by the wide-gap passes, so the final gap=1 passes usually need very few swaps. The loop continues until gap has reached 1 and a pass completes with no swaps.
та же идея, что у shell sort, но применённая к bubble sort вместо insertion sortthe same idea as shell sort, but applied to bubble sort instead of insertion sort
void comb_sort(std::vector<int>& a) {
int n = (int)a.size();
int gap = n;
const double shrink = 1.3;
bool swapped = true;
while (gap > 1 || swapped) {
gap = int(gap / shrink);
if (gap < 1) gap = 1;
swapped = false;
for (int i = 0; i + gap < n; ++i) {
if (a[i] > a[i + gap]) {
std::swap(a[i], a[i + gap]);
swapped = true;
}
}
}
}Жёлтая пара — текущее сравнение на расстоянии gap. Обратите внимание, как на широких gap элементы совершают большие прыжки сразу — это и есть механизм, устраняющий "черепах".The yellow pair is the current comparison at distance gap. Notice how at wide gaps elements make large jumps immediately — this is the exact mechanism that eliminates "turtles."
нажмите «Вперёд» или «Играть», чтобы начатьpress "Forward" or "Play" to begin
Строгий анализ худшего случая даёт Θ(n²) — так же, как у bubble sort, и это не удивительно: финальные проходы с gap=1 в худшем случае всё ещё могут требовать Θ(n) перестановок каждый, и таких проходов может быть Θ(n). На практике, однако, comb sort с shrink-фактором 1.3 эмпирически ведёт себя как O(n log n) на большинстве входов — устраняя почти все "дальние" инверсии за логарифмическое число широких проходов, оставляя гораздо меньше работы финальным проходам с малым gap. Строгого доказательства этой эмпирической границы для общего случая не существует — как и в случае shell sort (2.2.1.9), поведение зависит от свойств shrink-последовательности, изученных в основном экспериментально.A strict worst-case analysis gives Θ(n²) — same as bubble sort, which isn't surprising: the final gap=1 passes can still, worst case, need Θ(n) swaps each, and there can be Θ(n) such passes. In practice, however, comb sort with a 1.3 shrink factor empirically behaves like O(n log n) on most inputs — removing nearly all "long-range" inversions in a logarithmic number of wide passes, leaving far less work for the final small-gap passes. No rigorous proof of this empirical bound exists for the general case — as with shell sort (2.2.1.9), the behavior depends on properties of the shrink sequence studied mostly experimentally.
Один известный практический нюанс: значение shrink = 1.1 (не 1.3) вызывает специфическую проблему — на определённых входах два-три последних элемента продолжают чередоваться местами бесконечно на gap=1 и gap=2 ("черепахи-близнецы"), что исправляется небольшим хаком ("если gap равен 9 или 10, установить gap = 11") — деталь, обнаруженная эмпирически создателями алгоритма, а не выведенная теоретически.One well-known practical wrinkle: a shrink factor of 1.1 (not 1.3) causes a specific issue — on certain inputs, the last two or three elements keep swapping back and forth indefinitely at gap=1 and gap=2 ("turtle pairs"), fixed by a small hack ("if gap is 9 or 10, set gap = 11") — a detail discovered empirically by the algorithm's creators, not derived theoretically.
Comb sort иногда встречается в игровых движках и графических пайплайнах для сортировки небольших списков (например, полупрозрачных объектов по глубине) — простая реализация без рекурсии и без дополнительной памяти, при этом заметно быстрее bubble/insertion sort на практике.Comb sort occasionally shows up in game engines and graphics pipelines for sorting small lists (e.g. transparent objects by depth) — a simple, recursion-free, allocation-free implementation that's noticeably faster than bubble/insertion sort in practice.
Comb sort часто приводят как пример алгоритма, чьё практическое поведение (близкое к O(n log n)) существенно лучше доказанной верхней границы (Θ(n²)) — полезный контрпример к идее, что теоретическая сложность всегда точно предсказывает реальную производительность.Comb sort is often cited as an example of an algorithm whose practical behavior (close to O(n log n)) substantially beats its proven upper bound (Θ(n²)) — a useful counterexample to the idea that theoretical complexity always precisely predicts real-world performance.