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 | [1] |
| Legjobb időbonyolultság | |
| Átlagos idő bonyolultság | , ahol az inkrementumok száma[1] |
| Legrosszabb tár bonyolultság | |
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[szerkesztés]
10 ezer kevert egész szám rendezése CPU másodpercben:
Quicksort: 0,0038
Combsort: 0,0042
Bubblesort: 1,36
Példakód[szerkesztés]
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ő.
