Fésűs rendezés : Futásidő összehasonlítások, Példakód, Jegyzetek, Kapcsolódó szócikkek Wikipédia, a szabad enciklopédia

Fésűs rendezés

Fésűs rendezés

A fésűs rendezésre egy példa
Kategória	rendezési algoritmus
Adatstruktúra	tömb
Legrosszabb időbonyolultság	$O(n^{2})$ ^[1]
Legjobb időbonyolultság	$O(n\log n)$
Átlagos idő bonyolultság	$\Omega (n^{2}/2^{p})$ , ahol $p$ az inkrementumok száma^[1]
Legrosszabb tár bonyolultság	$O(1)$

Nem tévesztendő össze a következővel: Összefésüléses rendezés.

A fésűs rendezés (combsort) algoritmus egy tömb elemeinek sorba rendezésére. A buborékrendezés egy javított módszere. A buborékrendezés talán az összes rendezési algoritmus közül a legrosszabb, azonban egy egyszerű módosítással úgy felgyorsítható, hogy a gyorsrendezés sebességével vetekszik. Az eredeti fésűs rendezést Stephen Lacey és Richard Box fejlesztette, és a Byte Magazine publikálta 1991-ben.

Futásidő összehasonlítások

10 ezer kevert egész szám rendezése CPU másodpercben:
Quicksort: 0,0038
Combsort: 0,0042
Bubblesort: 1,36

Példakód

C# kódja:

 int gap=n;                                //az a táv, mely az összehasonlítandókat elválasztja
 for (;;)
     {
         gap=(gap*10)/13;                  //konvertál egészre ha kell
         if (gap==9 || gap==10) gap=11;
         if (gap<1) gap=1;
         bool csere_volt=false;
         for (int i=0; i<n-gap; i++)
             {
                 int j=i+gap;
                 if (a[i]>a[j])
                     {
                         int cs=a[i];
                         a[i]=a[j];
                         a[j]=cs;
                         csere_volt=true;
                     }
             }
                 if (gap==1 && !csere_volt) break;
    }

10 ezer elemű tömbön végzett kísérletek szerint a fésűs rendezés alig rosszabb a gyorsrendezésnél (10%-kal); a változtatás a buborékrendezéshez képest nem nagy. Ugyanakkor nem kell gondoskodni az eleve rendezett esetről, ami a gyorsrendezést nagyon lelassítja. A gap beállításával először a távollevő elemeket rendezzük. Ezután a gap csökken, míg végül egy lesz. Ez esetben azonos a program a buborékrendezéssel; következésképpen korrekt. Lacey és Richard Box megmutatta, hogy a gap minden lépésben 1,3-mal osztandó. Továbbá felfedezték, hogy 9 és 10 nem alkalmas gap-nek, és 11-gyel helyettesítendő.