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 |
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.
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
- ↑ a b 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