comb sort

comb sort (tsz. comb sorts)

1. (informatika) fésűs rendezés

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.

1. 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;
   

2. 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));
   

3. 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
   • Végiglépkedünk az indexeken i = 0 … n-gap-1, és ha a > a, akkor cseréljük őket és swapped = true-t állítunk.

4. 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

• A gap kezdetben a tömbhossz, majd minden iterációban gap/shrink lesz, de soha nem esik 1 alá.
• A 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.
• A std::swap segéd segítségével kedvező, helyben történő csere valósul meg.

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.

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.

• Közepes méretű tömbök (néhány ezres nagyságrendig), ahol már az O(n²) algoritmusok túl lassúak lehetnek, de az egyszerű implementáció értékes.
• Beágyazott rendszerek, ahol korlátozott memóriakeret mellett a helyigény fontosabb, mint a legjobb futási idő.
• Tanulási céllal: jó példa az algoritmusok gap-manipulációjára és a buborékrendezés továbbfejlesztésére.

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.

• comb sort - Szótár.net (en-hu)
• comb sort - Sztaki (en-hu)
• comb sort - Merriam–Webster
• comb sort - Cambridge
• comb sort - WordNet
• comb sort - Яндекс (en-ru)
• comb sort - Google (en-hu)
• comb sort - Wikidata
• comb sort - Wikipédia (angol)