Üdvözlöm, Ön a
radix sort szó jelentését keresi. A DICTIOUS-ban nem csak a
radix sort szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
radix sort szót egyes és többes számban mondani. Minden, amit a
radix sort szóról tudni kell, itt található. A
radix sort szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
radix sort és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
radix sort (tsz. radix sorts)
- (informatika) radix rendezés
A radix sort egy hatékony, nem összehasonlító rendezési algoritmus, amely számokat vagy karakterláncokat rendez a számjegyek vagy karakterek helyi értékei alapján, legkevésbé jelentős helyi értéktől a legjelentősebb felé haladva (vagy fordítva).
Hogyan működik a radix sort?
- Bemenet: Egy sorozat szám vagy karakterlánc, amelyeket helyi értékük alapján akarunk rendezni.
- A rendezés helyi értékek szerint rétegenként történik:
- Például számok esetén a legkisebb helyi értéktől (egyesek helye) kezdve rendezünk, majd a tízesek, százasok stb. szerint.
- Minden réteg rendezése stabil rendezőalgoritmussal (például counting sorttal vagy bucket sorttal) történik.
- A rétegek sorrendje meghatározza a rendezés típusát:
- LSD (Least Significant Digit): legkevésbé jelentős helyi értéktől haladunk a legjelentősebb felé.
- MSD (Most Significant Digit): a legjelentősebb helyi értéktől haladunk a legkevésbé jelentősebb felé.
Példa LSD radix sort működésére számokkal
Bemenet:
- Rendezés az egyesek helye szerint:

- Rendezés a tízesek helye szerint:

- Rendezés a százasok helye szerint:

Idő- és térbonyolultság
- Időbonyolultság:
, ahol
a számjegyek (vagy karakterek) száma,
az elemek száma,
a lehetséges értékek száma egy számjegyben (pl. 10 számjegy esetén).
- Hatékony nagy adatmennyiség esetén, különösen, ha
viszonylag kicsi.
- Nem összehasonlító algoritmus, nem függ az elemek relatív nagyságától.
Előnyök és hátrányok
Előnyök
|
Hátrányok
|
Gyors nagy elemszámú rendezésnél
|
Csak egész számokra vagy karakterekre jól alkalmazható
|
Lineáris idő feltételekkel
|
Több memóriaigény (stabil rendezés miatt)
|
Stabil rendezés
|
Bonyolultabb implementáció
|
Összefoglalás
Fogalom
|
Leírás
|
Radix sort
|
Többlépcsős, helyi értékeken alapuló rendezési algoritmus
|
Működés
|
Számjegyek vagy karakterek szerinti rétegzett rendezés
|
Idő:
|
|