Algoritmus řazení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. března 2020; ověření vyžaduje 41 úprav .

Algoritmus řazení je algoritmus pro řazení prvků v poli. V případě, že prvek v poli má více polí, pole, které slouží jako kritérium pořadí, se nazývá klíč řazení. V praxi číslo často funguje jako klíč a zbývající pole ukládají některá data, která neovlivňují činnost algoritmu.

Historie

První prototypy moderních metod třídění se objevily již v 19. století. V roce 1890 vytvořil Američan Herman Hollerith první statistický tabulátor , elektromechanický stroj určený k automatickému zpracování informací zaznamenaných na děrných štítcích, aby urychlil zpracování dat ze sčítání v USA [1] . Hollerithův stroj měl speciální „třídicí box“ s 26 vnitřními oddíly. Při práci se strojem byla obsluha povinna vložit děrný štítek a spustit rukojeť. Díky vyraženým otvorům na děrném štítku byl uzavřen určitý elektrický obvod a indikace číselníku s ním spojeného se zvýšila o jedničku. Současně bylo otevřeno jedno z 26 vík třídicího boxu a do odpovídajícího oddělení byl přesunut děrný štítek, načež bylo víko uzavřeno. Tento stroj umožnil zpracovat cca 50 karet za minutu, což zrychlilo zpracování dat 3x. Pro sčítání v roce 1900 Hollerith vylepšil stroj automatizací podávání karet [1] . Provoz Hollerithova třídicího stroje se opíral o radixové metody třídění . Strojní patent uvádí řazení „individuálně pro každý sloupec“, ale neuvádí pořadí. Další podobný stroj, patentovaný v roce 1894 Johnem Gorem, zmiňuje třídění ze sloupce desítek [2] . Metoda třídění, počínaje sloupcem jednotek, se poprvé objevuje v literatuře koncem 30. let 20. století [3] . V této době již třídicí stroje umožňovaly zpracovat až 400 karet za minutu [4] .

V budoucnu se ukázalo, že historie algoritmů je spojena s vývojem elektronických počítačů . Podle některých zdrojů se právě třídicí program stal prvním programem pro počítače. Někteří počítačoví designéři, zejména vývojáři EDVAC , označili problém třídění dat za nejtypičtější nenumerický úkol pro počítače. V roce 1945 John von Neumann vyvinul slučovací třídicí programy pro testování řady příkazů pro EDVAC . V témže roce německý inženýr Konrad Zuse vyvinul program pro jednoduché vkládání třídění . V této době se již objevily rychlé specializované třídičky, ve srovnání s nimiž byla hodnocena efektivita vyvinutých počítačů [4] . První publikovanou diskusí o třídění pomocí počítače byla přednáška Johna Mauchlyho v roce 1946. Mauchly ukázal, že třídění může být užitečné i pro numerické výpočty, popsal jednoduché metody řazení vkládáním a binárním vkládáním a radixové řazení s částečnými průchody. Později spoluzaložil Eckert-Mauchly Computer Corporation s inženýrem Johnem Eckertem, aby vyrobil některé z prvních elektronických počítačů BINAC a UNIVAC [5] . Spolu se známými vnitřními třídícími algoritmy se objevily i externí třídící algoritmy , jejichž vývoj byl usnadněn omezeným množstvím paměti prvních počítačů [4] . Zejména byly navrženy metody vyváženého dvoucestného bitového třídění a vyváženého dvoucestného slučování [5] .

V roce 1952 již bylo v praxi mnoho metod vnitřního třídění, ale teorie byla poměrně špatně rozvinutá [6] . V říjnu 1952 poskytl Daniel Goldenberg pět metod třídění s analýzou nejlepšího a nejhoršího případu pro každou z nich. V roce 1954 Harold Seward rozvinul Goldenbergovy myšlenky a také analyzoval externí metody třídění. Howard Demuth v roce 1956 uvažoval o třech abstraktních modelech problému řazení: pomocí kruhové paměti, lineární paměti a paměti s náhodným přístupem. Pro každý z těchto problémů autor navrhl optimální nebo téměř optimální metody třídění, které pomohly propojit teorii s praxí [7] . Vzhledem k malému počtu lidí spojených s výpočetní technikou se tyto zprávy v „otevřené literatuře“ neobjevily. První velký přehledový článek o třídění, který vyšel v tisku v roce 1955, byla práce J. Hoskena, ve které na základě prospektů výrobců popsal veškerá tehdy dostupná speciální zařízení a způsoby třídění pro počítače. V roce 1956 E. Friend ve své práci analyzoval matematické vlastnosti velkého počtu interních a externích třídicích algoritmů a navrhl některé nové metody [8] .

Od té doby bylo navrženo mnoho různých třídicích algoritmů: například výpočet adresy v roce 1956; merge with insertion, exchange radixsort , kaskádové merge a Shellova metoda v roce 1959, polyphase merge a tree insertions v roce 1960, oscilační řazení a Hoareho quicksort v roce 1962, Williamsův heapsort a exchangesort s Batcherovým sloučením v roce 1964. Koncem 60. let také došlo k intenzivnímu rozvoji teorie třídění [9] . Algoritmy, které se objevily později, byly v mnoha ohledech variacemi již známých metod. Rozšířily se metody adaptivního třídění zaměřené na rychlejší provádění v případech, kdy vstupní sekvence splňuje předem stanovená kritéria [9] .

Problémové prohlášení

klíč , který řídí proces třídění. Na sadě klíčů je definován vztah pořadí "<" tak, že pro všechny tři hodnoty klíče jsou splněny následující podmínky [10] : $K_{j}$ $a,b,c$

zákon trichotomie : buď, nebo, nebo; $a<b$ $a>b$ $a=b$
zákon tranzitivity : jestliže a , pak . $a<b$ $b<c$ $a<c$

Tyto podmínky definují matematický koncept lineárního nebo dokonalého uspořádání a množiny, které je splňují, lze třídit většinou metod [10] .

Úkolem třídění je najít takovou permutaci záznamů s indexy , za kterými by byly klíče umístěny v neklesajícím pořadí [10] : $p(1)p(2)\tečky p(n)$ $\{1,2,\tečky ,N\}$

{\displaystyle K_{p(1)}\leqslant K_{p(2)}\leqslant \dots \leqslant K_{p(n)))

Řazení se nazývá stabilní , pokud nemění vzájemnou polohu prvků se stejnými klíči [10] :

p(i)<p(j)

pro jakékoli a .

{\displaystyle K_{p(i)}=K_{p(j)))

i<j

Způsoby třídění lze rozdělit na interní a externí . Interní třídění se používá pro data, která se vejdou do paměti RAM, díky čemuž jsou z hlediska datových struktur flexibilnější. Při externím třídění nejsou data umísťována do RAM a je zaměřena na dosahování výsledků v podmínkách omezených zdrojů [11] .

Vyhodnocení algoritmu řazení

Třídicí algoritmy jsou hodnoceny pro rychlost provádění a efektivitu paměti:

Čas je hlavním parametrem charakterizujícím rychlost algoritmu. Také se nazývá výpočetní složitost . Pro řazení je důležité nejhorší , průměrné a nejlepší chování algoritmu z hlediska mohutnosti vstupní množiny A . Je-li vstupem do algoritmu nastaveno A , pak značíme n = | A |. Pro typický algoritmus je dobré chování O ( n log n ) a špatné chování je O ( n 2 ) . Ideální chování pro uspořádání je O ( n ) . Algoritmy řazení, které používají pouze operaci porovnání abstraktního klíče, vždy potřebují alespoň srovnání. Existuje však třídicí algoritmus O ( n log log n ) od Yijie Han , který využívá skutečnosti, že klíčový prostor je omezený (je extrémně složitý a O -notace skrývá velmi velký koeficient, což znemožňuje aplikaci v každodenní praxe) [12] . Existuje také koncept třídicích sítí . Za předpokladu, že je možné provádět několik porovnání současně (například při paralelním počítání ), je možné seřadit n čísel v O (log 2 n ) operacích. V tomto případě musí být číslo n známé předem;
Paměť – řada algoritmů vyžaduje přidělení další paměti pro dočasné ukládání dat. Tyto algoritmy obvykle vyžadují paměť O (log n ) . Vyhodnocení nebere v úvahu prostor, který zabírá původní pole, a náklady nezávislé na vstupní sekvenci, například pro uložení programového kódu (protože to vše spotřebuje O (1) ). Algoritmy řazení, které nespotřebovávají další paměť, se označují jako řazení na místě .

O ( n log n ) optimalita obecně

V obecném případě problém řazení předpokládá, že jedinou nezbytně dostupnou operací s prvky je porovnávání. Odpověď na porovnání prvků a může být jedna ze dvou možností: nebo . Pokud tedy algoritmus v průběhu práce provádí srovnání, existují pouze možné kombinace odpovědí na ně. $A$ $b$ $a\leq b$ $a>b$ $k$ $2^k$

Počet permutací prvků je . Aby bylo možné surjektivně mapovat množinu kombinací odpovědí na množinu všech permutací, musí být počet srovnání alespoň (protože porovnání je jediná povolená operace). $n$ $n$ $\log _{2}{n!}$

Vezmeme- li logaritmus Stirlingova vzorce , můžeme zjistit, že [13] $\log _{2}{n!}=\log _{2}{\left({\sqrt {2\pi n}}\left({\frac {n}{e}}\right) ^{n}\right)}=n\log n+O(n)=\Omega (n\log n)$

Vlastnosti a typy

Stabilita - stabilní řazení nemění vzájemnou polohu prvků se stejnými klíči [14] .
Přirozenost chování - efektivita metody při zpracování již objednaných nebo částečně objednaných dat. Algoritmus se chová přirozeně, pokud bere v úvahu tuto charakteristiku vstupní sekvence a funguje lépe.
Použití operace porovnání. Algoritmy, které k řazení používají srovnání mezi prvky, se nazývají založené na porovnání. Minimální složitost nejhoršího případu pro tyto algoritmy je ( ), liší se však flexibilitou aplikace. Pro speciální případy (datové typy) existují efektivnější algoritmy. $Ó$ $n\cdot\log n$

Další důležitou vlastností algoritmu je jeho rozsah. Existují dva hlavní typy objednávek:

Interní řazení funguje na polích, která se zcela vejdou do paměti RAM s náhodným přístupem k jakékoli buňce. Data se obvykle objednávají na stejném místě bez dalších nákladů.
- Paměťové stránkování a ukládání do mezipaměti jsou široce používány v moderních architekturách osobních počítačů . Algoritmus řazení by měl dobře fungovat s použitými algoritmy ukládání do mezipaměti a odkládání.
Externí třídění funguje na velkých paměťových zařízeních, ale ne s náhodným přístupem, ale sekvenčním (uspořádání souborů), to znamená, že v tuto chvíli je „viditelný“ pouze jeden prvek a náklady na převíjení jsou ve srovnání s pamětí nepřiměřeně vysoké. To ukládá algoritmu některá další omezení a vede ke speciálním metodám řazení, které obvykle využívají další místo na disku. Přístup k datům v externí paměti je navíc mnohem pomalejší než operace s RAM.
- Přístup k médiím se provádí sekvenčním způsobem: v každém okamžiku lze číst nebo zapisovat pouze prvek následující za aktuálním.
- Množství dat jim neumožňuje vejít se do RAM.

Algoritmy jsou také klasifikovány podle:

potřeba další paměti nebo její absence
potřeba znalostí o struktuře dat, které přesahují srovnávací operaci, nebo jejich nedostatek

Přehled nejpopulárnějších třídicích algoritmů

Algoritmus	Popis	Čas dokončení		Náklady na paměť	Poznámka
Algoritmus	Popis	Při nejhorším	Průměrný	Nejlepší scénář	Poznámka
Perzistentní třídicí algoritmy
Bublinové řazení _ _ _	Iteruje pole, porovnává po sobě jdoucí páry prvků a zaměňuje je, pokud jsou ve špatném pořadí.	$O(n^{2})$	$O(n^{2})$	$O(1)$	V procesu třídění se v horní části pole „objeví“ minimální prvek, který připomíná bublinu
Míchací druh ( angl. Cocktail sort )	Obousměrné, optimalizované třídění bublin	$O(n^{2})$	$O(n^{2})$	$O(1)$
Řazení vložení _ _ _	Prvky vstupní sekvence jsou zkoumány jeden po druhém a každý nový prvek je umístěn na vhodné místo mezi dříve uspořádané prvky.	$O(n^{2})$	$O(n^{2})$	$O(1)$
Gnome sorting ( angl. Gnome sort )	Kříženec vkládání a bublinových druhů .	$O(n^{2})$	$O(n^{2})$	$O(1)$	Název pochází z domnělého chování zahradních trpaslíků při třídění řady zahradních květináčů.
Sloučit řazení _ _ _	Rekurzivně seřadí poloviny pole a poté je spojí do jedné	$O(n\log {n})$	$O(n\log {n})$	$Na)$
Třídění pomocí binárního stromu ( angl. Tree sort )	Na základě počátečních dat je vytvořen binární vyhledávací strom , ve kterém jsou postupně shromažďovány minimální hodnoty	$O(n^{2})$	$O(n\log {n})$	$Na)$
Řazení Timsort _ _ _ _	Kříženec řazení vložení a řazení sloučení . Vycházíme z předpokladu, že při řešení praktických problémů se vstupní pole často skládá z seřazených podpolí	$O(n\log {n})$	$O(n\log {n})$	$O(1)$
Nestabilní třídicí algoritmy
Seřadit výběr _ _ _	Rozdělí vstupní pole na uspořádané a neuspořádané části. Poté postupně přenese nejmenší prvky z druhé do první části.	$O(n^{2})$	$O(n^{2})$	$O(1)$
Hřebenové řazení _ _ _	Modifikace bublinového řazení , ve které je vzdálenost mezi porovnávanými dvojicemi hodnot jiná než 1	$O(n^{2})$	$O(n^{2}/2^{p})$	$O(1)$	Navzdory větší algoritmické složitosti bude pro nepříliš velké velikosti polí hřebenové řazení efektivnější než rychlé řazení .
Shell seřadit _ _ _	Modifikace řazení vložení , ve které je vzdálenost mezi porovnávanými dvojicemi hodnot jiná než 1	$O(n^{2})$	$O(n\log ^{2}{n})$	$O(1)$
Řazení haldy (třídění haldy, řazení haldy)	Na základě počátečních dat se sestaví binární halda , ve které se postupně shromažďují minimální hodnoty	$O(n\log {n})$	$O(n\log {n})$	$Na)$
Smoothsort _ _ _ _	Úprava heapsortu , optimalizace řazení částečně uspořádaného pole	$O(n\log {n})$	$O(n\log {n})$	$Na)$
Rychlé třídění _ _ _ _	Je vybrán referenční prvek p. Všechny klávesy menší než p se přesunou doleva a všechny klávesy větší nebo rovné p se přesunou doprava. Dále je algoritmus rekurzivně aplikován na každou z částí	$O(n^{2})$	$O(n\log {n})$	$O(1)$
Introspektivní třídění _ _ _	Hybrid rychlého a velkého množství	$O(n\log {n})$	$O(n\log {n})$	$Na)$
Stupid sort ( eng. Stooge sort )	V případě potřeby zamění první a poslední prvek pole. Poté rozdělí pole na tři části, z nichž každá běží rekurzivně	$O(n^{\log {3}/\log {1.5)))$ $=O(n^{2,709...})$	$O(n^{2,709...})$	$O(1)$	Metoda je pojmenována po americké komediální skupině Three Stooges . Podobnost spočívá v tom, že algoritmus šíleně spěchá přes již seřazené třetiny pole.
Nepraktické třídicí algoritmy
Bogosort	Pole je náhodně zamícháno, dokud není seřazeno.	Neomezený	$O(n!)$	$O(1)$	Používá se pouze pro akademické účely
Seřadit podle permutace	Vygenerují se všechny možné sekvence pole, ze kterých se vybere uspořádaná sekvence.	$O(n!)$	$O(n!)$	$Na)$	Používá se pouze pro akademické účely
Gravitační třídění ( English Bead sort )	Čísla jsou reprezentována jako korálky na špendlíkech, poté seřazená podle gravitace	$O(\sqrt{n})$	$O(\sqrt{n})$	$O(n^{2})$	Vyžaduje specializovaný hardware
Algoritmy nejsou založeny na srovnání
Blokovat řazení _ _ _	Prvky jsou rozděleny do bloků podle rozsahu hodnot, z nichž každá je pak rekurzivně tříděna	$O(n^{2})$	$O(n^{2}+n/k+k)$	$O(n+k)$	$k$ - předem stanovený počet košů
Bitové řazení ( eng. Radix sort )	Pole se třídí podle bitového porovnávání čísel	$O(wn)$	$O(wn)$	$Na)$	$w$ je počet bitů potřebných k uložení každého klíče.
Počítání řazení _ _ _	Počítá se počet výskytů každého celého čísla z rozsahu klíčů v poli. Poté se vytisknou hodnoty všech nenulových hodnot	$O(n+k)$	$O(n+k)$	$O(n+k)$	$k$ - maximální hodnota klíčových prvků

Třídicí řetězce

Jednou z běžných aplikací třídicích algoritmů je třídění řetězců. Zobecněný algoritmus může vypadat takto: nejprve je sada řetězců setříděna podle prvního znaku každého řetězce, poté je každá podmnožina řetězců, které mají stejný první znak, setříděna podle druhého znaku a tak dále, dokud nejsou seřazeny všechny řetězce. . V tomto případě je chybějící znak (při porovnávání řetězce délky N s řetězcem délky N + 1) považován za menší než jakýkoli znak.

Použití této metody na řetězce, které jsou čísly v přirozeném zápisu, poskytuje neintuitivní výsledky: například "9" je větší než "11", protože první znak prvního řetězce má větší hodnotu než první znak druhého. K vyřešení tohoto problému může třídicí algoritmus převést tříděné řetězce na čísla a seřadit je jako čísla. Takový algoritmus se nazývá „numerické řazení“ a dříve popsaný algoritmus se nazývá „řetězcové řazení“. V praxi je také účinným způsobem, jak vyřešit problém řazení řetězců obsahujících čísla, přidat před číslo určitý počet nul, takže "011" bude považováno za větší než "009".

Viz také

Poznámky

↑ 1 2 Knuth, 2007 , str. 416.
↑ Knuth, 2007 , str. 417.
↑ Knuth, 2007 , str. 417-418.
↑ 1 2 3 Knut, 2007 , str. 418.
↑ 1 2 Knuth, 2007 , str. 419.
↑ Knuth, 2007 , str. 420.
↑ Knuth, 2007 , str. 420-421.
↑ Knuth, 2007 , str. 421.
↑ 1 2 Knuth, 2007 , str. 422.
↑ 1 2 3 4 Knut, 2007 , str. 22.
↑ Knuth, 2007 , str. 23.
↑ Han, Yijie. Deterministické třídění v O(n log log n) čase a lineárním prostoru // Journal of Algorithms. Poznání, informatika a logika. - 2004. - T. 50 , č. 1 . - S. 96-105 . - doi : 10.1016/j.jalgor.2003.09.001 .
↑ Donald Knuth. 5.3.1. Řazení s minimálním počtem srovnání // The Art of Programming. - 2. — Williams, 2002.
↑ Knuth, 2007 .

Literatura

Knut D. E. Umění programování. Svazek 3. Třídění a vyhledávání = The Art of Computer Programming. Svazek 3. Třídění a vyhledávání / ed. V. T. Tertyshny (5. kap.) a I. V. Krasikov (6. kap.). - 2. vyd. - Moskva: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Robert Sedgwick. Základní algoritmy v C. Základy/Datové struktury/Řazení/Vyhledávání. - Petrohrad. : DiaSoftYUP, 2003. - S. 672. - ISBN 5-93772-081-4 .
Magnus Lie Hetland. Algoritmy Pythonu: Zvládnutí základních algoritmů v jazyce Python. - Apress, 2010. - 336 s. - ISBN 978-1-4302-3237-7 .

Odkazy

Algoritmy řazení
Teorie	Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna	bublina Míchání Trpaslíci Rychle Hřeben Řazení sudé-liché bitový
Výběr	Výběr Pyramidový Hladký
vložky	vložky shella strom
fúze	fúze
Žádné srovnání	Počítací blok
hybridní	introsort Timsort
jiný	Topologické sítí biton
nepraktický	Bogosort Stooge řazení lívanec pomalý