Fésűs 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.

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	${\displaystyle O(n^{2})}$[1]
Legjobb időbonyolultság	${\displaystyle O(n\log n)}$
Átlagos idő bonyolultság	${\displaystyle \Omega (n^{2}/2^{p})}$, ahol ${\displaystyle p}$ az inkrementumok száma[1]
Legrosszabb tár bonyolultság	${\displaystyle O(1)}$

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

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

Jegyzetek

1. doi:10.1016/S0020-0190(00)00223-4

Kapcsolódó szócikkek

• Rendezés (programozás)
• Koktélrendezés
• Buborékrendezés
• Gyorsrendezés
• Kupacrendezés
• Beszúrásos rendezés

• Informatikai portál • összefoglaló, színes tartalomajánló lap