Radix sort

radix sort
Autor	Hollerith, Herman
účel	Algoritmus řazení
Datová struktura	pole
nejhorší čas	, kde w je počet bitů potřebných k uložení každého klíče.
Náklady na paměť
Mediální soubory na Wikimedia Commons

Bitové třídění ( anglicky  radix sort ) je třídicí algoritmus , který běží v lineárním čase. Existují stabilní možnosti.

Algoritmus

Původně určen pro třídění celých čísel zapsaných jako číslice. Ale protože v paměti počítačů jsou jakékoli informace zaznamenány jako celá čísla, je algoritmus vhodný pro třídění libovolných objektů, jejichž záznam lze rozdělit na "číslice" obsahující srovnatelné hodnoty. Tímto způsobem můžete například třídit nejen čísla zapsaná jako sada čísel, ale také řetězce, které jsou sadou znaků, a obecně libovolné hodnoty v paměti, reprezentované jako sada bajtů.

Porovnání se provádí bit po bitu: nejprve se porovnají hodnoty jedné krajní číslice a prvky se seskupí podle výsledků tohoto srovnání, poté se porovnají hodnoty další sousední číslice a prvky jsou buď seřazeny podle výsledků porovnání hodnot této číslice ve skupinách vytvořených v předchozím průchodu, nebo jsou přeřazeny jako celek, ale zachovávají relativní pořadí dosažené předchozím řazením. Poté se totéž provede pro další vypouštění a tak dále až do konce.

Vzhledem k tomu, že je možné porovnávané záznamy vzájemně zarovnávat různými směry, existují v praxi dvě možnosti tohoto řazení. U čísel se nazývají z hlediska významnosti číslic čísla a dopadá to takto: zápisy čísel můžete zarovnat směrem k méně významným číslicím (na pravé straně směrem k jedničkám, nejméně významné číslici, LSD ) nebo více platných číslic (na levé straně, od významnějších číslic, nejvýznamnější číslice, MSD).

Pomocí LSD třídění (třídění se zarovnáním podle nejméně významné číslice vpravo, k jedničkám) se získá pořadí, které je vhodné pro čísla. Například: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. To znamená, že zde jsou hodnoty nejprve setříděny po jednotkách, poté setříděny po desítkách, přičemž třídění po jednotkách zůstává uvnitř po desítkách, pak po stovkách, třídění po desítkách a jednotkách v rámci stovek atd.

Třídění MSD (vysoké pořadí, zarovnáno doleva) má za následek abecední pořadí, které je vhodné pro řazení řádků textu. Například "b, c, d, e, f, g, h, i, j, ba" budou řazeny jako "b, ba, c, d, e, f, g, h, i, j". Pokud MSD použijeme na čísla uvedená v příkladu, dostaneme sekvenci 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Informace o skupinách můžete shromažďovat při každém průchodu různými způsoby – například v seznamech, ve stromech, v polích, vypisováním buď samotných prvků, nebo jejich indexů atd.

Existuje nestabilní verze rekurzivního bitového řazení, které se provádí přímo v seřazeném poli: při prvním průchodu jde pohyb k sobě, na začátku pole se hledá prvek s 1 na první bitové číslici, na konci pole se hledá prvek s 0 na stejné číslici. Nalezené prvky se vymění a tak dále, dokud se příslušné indexy nepotkají. Na začátku pole, před bodem setkání indexů, jsou tedy shromážděny všechny prvky s bitem rovným 0 a za tímto indexem všechny prvky s bitem rovným 1. Poté lze rekurzivně zcela podobně iterujte výsledné podrozsahy pole, porovnejte hodnoty druhého a následujících bitů a přeskupte místa prvků.

Aplikace pro řádky ve variantě řazení košíku

Košík třídění můžete použít k třídění podle pozice . Každá kategorie se jede dvakrát. Při prvním průchodu se započítá počet určitých hodnot v této kategorii. Poté se pro každou možnou hodnotu připraví pole pro uložení prvků s touto hodnotou. Během druhého průchodu se do těchto polí zapisují samotné prvky. Efektivní implementace je možná použitím pole řetězcových odkazů namísto samotných řetězců a dalšího pole "velikostí přihrádek" inicializovaných při prvním průchodu s počtem prvků v každém "přihrádce".

Druhý a následující průchod se provádějí samostatně na každém koši získaném v předchozím průchodu, přičemž se rozděluje na "podkoše" a porovnávají se druhý a následující znaky řetězců.

Operace končí, když je dosaženo maximální délky řetězce nebo když všechny "podkoše" mají délku 1.

Poznámky

Literatura

• Donald Knuth . Umění počítačového programování, díl 3. Třídění a vyhledávání = The Art of Computer Programming, díl 3. Třídění a vyhledávání. - 2. vyd. - M .: "Williams" , 2007. - S. 192-201. — ISBN 5-8459-0082-4 .

Odkazy

• Visualizer1  je Java applet.
• Visualizer2  je Java applet.
• Implementace algoritmu v C++ Archivováno 27. července 2019 na Wayback Machine .