Radix rendezés

radix rendezés
Szerző	Hollerith, Herman
célja	Rendezési algoritmus
Adatstruktúra	sor
legrosszabb idő	, ahol w az egyes kulcsok tárolásához szükséges bitek száma.
A memória költsége
Médiafájlok a Wikimedia Commons oldalon

A bitenkénti rendezés ( ang.  radix sort ) egy lineáris időben futó rendezési algoritmus . Vannak stabil lehetőségek.

Algoritmus

Kezdetben számjegyként írt egész számok rendezésére szolgált. De mivel a számítógépek memóriájában minden információ egész számként kerül rögzítésre, az algoritmus alkalmas bármilyen objektum rendezésére, amelyek rekordja összehasonlítható értékeket tartalmazó "számjegyekre" osztható. Például így nem csak a számkészletként írt számokat rendezheti, hanem a karakterkészleteket és általában a memóriában lévő tetszőleges értékeket is, amelyek bájtkészletként jelennek meg.

Az összehasonlítás bitenként történik: először egy szélső számjegy értékeit hasonlítjuk össze, és az összehasonlítás eredményei szerint csoportosítjuk az elemeket, majd a következő, szomszédos számjegy értékeit hasonlítjuk össze, és az elemek vagy ennek a számjegynek az előző lépésben kialakított csoportokon belüli összevetésének eredménye alapján vannak rendezve, vagy egészben átrendezve, de megőrizve az előző rendezéssel elért relatív sorrendet. Ezután ugyanezt megtesszük a következő kisütésnél, és így tovább a végéig.

Mivel lehetőség van az összehasonlított rekordok egymáshoz viszonyítására különböző irányban, ezért a gyakorlatban két lehetőség kínálkozik erre a rendezésre. A számok esetében a számjegyek jelentősége alapján hívják őket, és ez így alakul: a számok bevitelét kevésbé jelentős számjegyekhez igazíthatja (jobb oldalon egyek felé, legkisebb jelentőségű számjegy, LSD ) vagy több jelentős számjegy (bal oldalon, jelentősebb számjegyekből, legjelentősebb számjegy, MSD).

Az LSD rendezésnél (rendezés a legkisebb jelentőségű számjegyhez igazítva, jobbra, egyesekhez) a számoknak megfelelő sorrendet kapjuk. Például: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Ez azt jelenti, hogy itt az értékek először egyesek, majd tízesek szerint vannak rendezve, az egyesek szerint pedig bent marad tízesével, majd százával, a válogatás tízesével és az egységek százon belüli tartásával stb.

Az MSD rendezés (magas sorrendű, balra igazított) ábécé sorrendet eredményez, ami a szövegsorok rendezésére alkalmas. Például a „b, c, d, e, f, g, h, i, j, ba” a következőképpen lesz rendezve: „b, ba, c, d, e, f, g, h, i, j”. Ha az MSD-t alkalmazzuk a példában megadott számokra, akkor az 1, 10, 100, 2, 200, 201, 202, 21, 210, 9 sorozatot kapjuk.

Különböző módokon halmozhat fel információkat a csoportokról minden egyes lépésnél - például listákban, fákban, tömbökben, kiírhatja magukat az elemeket vagy indexeiket stb.

A rekurzív bitenkénti rendezésnek van egy instabil változata, amelyet közvetlenül a rendezett tömbben hajtanak végre: az első lépésben a mozgás egymás felé halad, a tömb elején egy olyan elemet keres, amelynek első bitszámjegye 1, a tömb végén egy olyan elemet keresünk, amelynek 0-a ugyanabban a számjegyben van. A talált elemek felcserélődnek, és így tovább, amíg a kérdéses indexek találkoznak. Így a tömb elején, az indexek találkozási pontja előtt összegyűjtjük az összes 0 bittel rendelkező elemet, majd az index után az összes 1-es bittel rendelkező elemet. Ekkor rekurzív módon teljesen hasonlóképpen lehet iterálja a tömb eredményül kapott altartományait, összehasonlítja a második és az azt követő bitek értékét, és átrendezi az elemek helyét.

Alkalmazás a kosár rendezési változatának soraihoz

A kosár rendezése a rang szerinti rendezéshez használható . Minden kategória kétszer indul. Az első lépésnél a rendszer megszámolja a kategóriába tartozó bizonyos értékek számát. Ezután minden lehetséges értékhez tömbök készülnek az adott értékű elemek tárolására. A második lépés során maguk az elemek kiíródnak ezekbe a tömbökbe. A hatékony megvalósítás akkor lehetséges, ha maguk a karakterláncok helyett karakterlánc-hivatkozások tömbjét használjuk, és az első lépésben inicializálva egy további "bin méretek" tömbjét az egyes "bin" elemek számával.

A második és az azt követő passzokat az előző passzban szerzett minden egyes kosarakon külön hajtják végre, "alkosarakra" osztva, és összehasonlítva a karakterláncok második és további karaktereit.

A művelet akkor ér véget, amikor eléri a maximális karakterlánchosszt, vagy amikor az összes "alkosár" 1 hosszúságú.

Jegyzetek

Irodalom

• Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Rendezés és keresés. - 2. kiadás - M . : "Williams" , 2007. - S. 192-201. — ISBN 5-8459-0082-4 .

Linkek

• A Visualizer1  egy Java kisalkalmazás.
• A Visualizer2  egy Java kisalkalmazás.
• Az algoritmus implementációja C++ nyelven Archiválva : 2019. július 27. a Wayback Machine -nél .