Törpe válogatás
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 1-jén felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .A Gnome sort ( eng. Gnome sort ) egy rendezési algoritmus , amely hasonló a beszúrások szerinti rendezéshez , de az utóbbitól eltérően a megfelelő helyre történő beszúrás előtt egy sor csere történik, mint a buborékos rendezésnél . A név a kerti törpék feltételezett viselkedéséből származik, amikor a kerti edények sorát rendezik.
A törpe válogatás a közönséges holland kerti törpe ( holland tuinkabouter ) technikáján alapul. Ez az a módszer, amellyel a kerti törpe virágcserepek sorát rendezi. Lényegében a jelenlegi és a korábbi kerti edényeket nézi: ha a megfelelő sorrendben vannak, akkor egy cserépedényt előre lép, ellenkező esetben felcseréli őket, és egy cserepet hátralép. Peremfeltételek: ha nincs előző pot, előre lép; ha nincs következő pot, akkor kész.
Dick Grun
Az algoritmus elvileg egyszerű, és nem igényel beágyazott hurkokat. Munkaidő . A gyakorlatban az algoritmus olyan gyorsan futhat, mint a beillesztési rendezés.
Az algoritmus megtalálja az első helyet, ahol két szomszédos elem rossz sorrendben van, és felcseréli őket. Kihasználja azt a tényt, hogy egy csere közvetlenül a felcserélt elemek előtt vagy után tud rossz sorrendben új párt produkálni. Nem teszi lehetővé az aktuális pozíció utáni elemek rendezését, így csak az átrendezett elemek előtti pozíciót kell ellenőrizni.
Leírás
Alul a rendezési pszeudokód látható. Ez egy optimalizált verzió, amely a j változót használja , hogy lehetővé tegye az előreugrást oda, ahol abbahagyta, mielőtt balra mozdulna, elkerülve a szükségtelen iterációkat és összehasonlításokat:
Példa:
Ha egy [4] [2] [7] [3] elemű tömböt a legnagyobbtól a legkisebbig szeretnénk rendezni, akkor a while ciklus iterációi során a következő történik:
- [4] [2] [7] [3] (kezdeti állapot: i == 1, j == 2);
- [4] [2] [7] [3] (nem történt semmi, de most i == 2, j == 3);
- [4] [7] [2] [3] (a[2] és a[1] felcserélése, most i == 1 és j == 3 állókép);
- [7] [4] [2] [3] (a[1] és a[0] felcserélése, most i == 3, j == 4);
- [7] [4] [3] [2] (a[3] és a[2] felcserélése, most i == 2, j == 4);
- [7] [4] [3] [2] (nem történt semmi, de most i == 4, j == 5);
- a ciklusnak vége, mert én nem vagyok < 4.
Optimalizálás
A gnome optimalizálás eredményeként a rendezés természetesen átalakul beszúrásos rendezéssé . Minden alkalommal, amikor a "gnome" új számot talál, a "gnome" bal oldalán lévő összes érték már rendezve van.
Linkek
- A módszer leírása és a gnome válogató programok listája .
| Rendezési algoritmusok | |
|---|---|
| Elmélet | Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső |
| Csere | |
| Választás | |
| Betétek | |
| egyesülés | |
| Nincs összehasonlítás | |
| hibrid | |
| Egyéb | |
| nem praktikus | |