radix sort

radix sort (tsz. radix sorts)

1. (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).

1. Bemenet: Egy sorozat szám vagy karakterlánc, amelyeket helyi értékük alapján akarunk rendezni.
2. 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.
3. Minden réteg rendezése stabil rendezőalgoritmussal (például counting sorttal vagy bucket sorttal) történik.
4. 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é.

Bemenet: ${\textstyle 170,45,75,90,802,24,2,66}$

• Rendezés az egyesek helye szerint: ${\textstyle 170,90,802,2,24,45,75,66}$
• Rendezés a tízesek helye szerint: ${\textstyle 802,2,24,45,66,170,75,90}$
• Rendezés a százasok helye szerint: ${\textstyle 2,24,45,66,75,90,170,802}$

• Időbonyolultság: ${\textstyle O(d\times (n+k))}$, ahol
  • ${\textstyle d}$ a számjegyek (vagy karakterek) száma,
  • ${\textstyle n}$ az elemek száma,
  • ${\textstyle k}$ 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 ${\textstyle d}$ viszonylag kicsi.
• Nem összehasonlító algoritmus, nem függ az elemek relatív nagyságától.

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ő ${\textstyle O(n)}$ feltételekkel	Több memóriaigény (stabil rendezés miatt)
Stabil rendezés	Bonyolultabb implementáció

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ő:	${\textstyle O(d\times (n+k))}$

• radix sort - Szótár.net (en-hu)
• radix sort - Sztaki (en-hu)
• radix sort - Merriam–Webster
• radix sort - Cambridge
• radix sort - WordNet
• radix sort - Яндекс (en-ru)
• radix sort - Google (en-hu)
• radix sort - Wikidata
• radix sort - Wikipédia (angol)