comb sort (tsz. comb sorts)
A comb sort (fésűrendezés) egy továbbfejlesztett változata a buborékrendezésnek, melyet Paul W. Estivill és Richard Box fejlesztett ki 1980 körül, később Stephen Lacey és Richard Box tette népszerűvé 1991-ben. Célja, hogy a buborékrendezés egyik gyenge pontját – a kis, a végén rekedt elemek lassú „felháborítását” – hatékonyabban kezelje. Ezt úgy éri el, hogy az összehasonlítások során nem csak szomszédos elemeket vizsgál, hanem kezdetben nagyobb „résen” (gap) átugorva párokat hasonlít össze, a gap értékét fokozatosan csökkentve egészen 1-ig.
Gap–érték inicializálása A gap kezdeti értékét általában a tömb hosszának 1,3-szorosával (pontosabban 1/1.3 ≈ 0.769
szorzóval) állítjuk be:
gap = n;
shrink = 1.3;
Gap csökkentése Minden iterációban a gap új értéke legyen a régi gap osztva a shrink faktorral, lefelé kerekítve, de legalább 1:
gap = max(1, int(gap / shrink));
Elemek összehasonlítása és cseréje Amíg a gap > 1 vagy történt legalább egy csere (swapped == true), fusson a ciklus:
swapped = false
i = 0 … n-gap-1
, és ha a > a
, akkor cseréljük őket és swapped = true
-t állítunk.Befejezés A ciklust akkor zárjuk le, amikor a gap = 1 és az adott átjárásban nem történt csere – ekkor a tömb rendezett.
Ez a megközelítés képes a „távoli” kis elemeket gyorsan a helyükre „fésülni”, majd a buborékrendezésre jellemző finomhangolással lezárni a rendezést.
CombSort(a, n):
gap = n
shrink = 1.3
swapped = true
while gap > 1 or swapped:
# Gap csökkentése
gap = max(1, floor(gap / shrink))
swapped = false
# Páros összehasonlítások adott réssel
for i = 0 to n - gap - 1:
if a > a:
swap a, a
swapped = true
#include <iostream>
#include <vector>
#include <cmath> // floor
void combSort(std::vector<int>& a) {
int n = static_cast<int>(a.size());
int gap = n;
const double shrink = 1.3;
bool swapped = true;
while (gap > 1 || swapped) {
// Résszűkítés
gap = static_cast<int>(floor(gap / shrink));
if (gap < 1) gap = 1;
swapped = false;
// Összehasonlítás és csere
for (int i = 0; i + gap < n; ++i) {
if (a > a) {
std::swap(a, a);
swapped = true;
}
}
}
}
int main() {
std::vector<int> arr = { 8, 4, 1, 56, 3, -44, 23, -6, 28, 0 };
std::cout << "Eredeti: ";
for (int x : arr) std::cout << x << ' ';
std::cout << "\n";
combSort(arr);
std::cout << "Rendezett: ";
for (int x : arr) std::cout << x << ' ';
std::cout << "\n";
return 0;
}
Magyarázat
gap
kezdetben a tömbhossz, majd minden iterációban gap/shrink
lesz, de soha nem esik 1 alá.swapped
logikai változó biztosítja, hogy még gap = 1 esetén is fusson egy teljes buborék-átjárás, ha az előző lépésben volt csere, így garantálva a rendezettséget.std::swap
segéd segítségével kedvező, helyben történő csere valósul meg.
Eshetőség | Időkomplexitás | Megjegyzés |
---|---|---|
Legjobb | O(n log n) | Ideális gap-sorozat esetén (ritka) |
Átlagos | O(n² / 2^p), p ≈ log (1/shrink) | Gyakorlati tapasztalatok: ~O(n^1.3) |
Legrosszabb | O(n²) | Szomszédos elemsor marad (gap=1 végéig) |
Helyigény | O(1) | Csak néhány segédváltozó |
Stabilitás | Nem | A csereelv miatt azonos értékek sorrendje változhat |
A comb sort tipikusan jelentősen gyorsabb a buborékrendezésnél és más O(n²) algoritmusoknál (pl. kiválasztásos rendezés) – különösen nagyobb tömbökön –, ugyanakkor nem éri el az O(n log n) algoritmusok (Quick Sort, Merge Sort) általános sebességét.
Tulajdonság | Bubble Sort | Comb Sort |
---|---|---|
Gap–kezelés | Igen (gap=1 állandó) | Dinamikus, 1 → n/1.3 → … → 1 |
Távoli csere | Nem | Igen |
Átlagos sebesség | O(n²) | ~O(n^1.3) |
Cserék száma | Sok (n^2/2) | Jelentősen kevesebb |
Kód komplexitás | Egyszerű | Kicsit bonyolultabb |
Míg a buborékrendezés minden lépésben csak a szomszédos elemeket vizsgálja, addig a comb sort lehetőséget ad nagyobb távolság alapján cserélni, ami felgyorsítja a rendezés korai fázisát.
A comb sort a buborékrendezésből kiinduló, gap-alapú „fésülős” megközelítéssel jelentősen javítja a tipikus O(n²) algoritmusok teljesítményét, különösen a nagyobb tömbökön. Helyben működik, minimális extra memóriát igényel, és viszonylag egyszerűen megvalósítható C++-ban. Bár a leggyorsabb általános rendezők (Quick Sort, Merge Sort) továbbra is előnyben vannak nagy adatmennyiségek esetén, a comb sort jó kompromisszumot kínál egyszerűség, kis helyigény és elfogadható futási idő között.