Algoritmus řazení - Sorting algorithm

Ve vědě o počítačích , je třídění algoritmus je algoritmus , který staví prvky seznamu do o pořadí . Nejčastěji používanými příkazy jsou číselné a lexikografické pořadí a to buď vzestupně, nebo sestupně. Efektivní třídění je důležité pro optimalizaci účinnosti jiných algoritmů (například vyhledávacích a slučovacích ), které vyžadují, aby vstupní data byla v seřazených seznamech. Třídění je také často užitečné pro kanonizaci dat a pro produkci výstupů čitelných pro člověka.

Formálně musí výstup jakéhokoli algoritmu třídění splňovat dvě podmínky:

1. Výstup je v monotónním pořadí (každý prvek není menší/větší než předchozí prvek, podle požadovaného pořadí).
2. Výstupem je permutace (přeuspořádání, ale zachování všech původních prvků) vstupu.

Pro optimální účinnost by měla být vstupní data uložena v datové struktuře, která umožňuje spíše náhodný přístup než ten, který umožňuje pouze sekvenční přístup .

Historie a pojmy

Od začátku práce na počítači přitahoval problém třídění velké množství výzkumů, možná kvůli složitosti jeho efektivního řešení navzdory jeho jednoduchému, známému tvrzení. Mezi autory raných algoritmů třídění kolem roku 1951 byla Betty Holberton , která pracovala na ENIAC a UNIVAC . Třídění bublin bylo analyzováno již v roce 1956. Asymptoticky optimální algoritmy jsou známy již od poloviny 20. století - stále se vymýšlejí nové algoritmy, přičemž široce používaný Timsort pochází z roku 2002 a druh knihovny byl poprvé publikován v roce 2006.

Algoritmy srovnávacího řazení mají základní požadavek na srovnání Ω ( n log n ) (některé vstupní sekvence budou vyžadovat násobek n log n srovnání, kde n je počet prvků v poli, které mají být tříděny). Algoritmy, které nejsou založeny na srovnávání, jako je například počítání , mohou mít lepší výkon.

Algoritmy řazení jsou převládající v úvodních hodinách informatiky , kde množství algoritmů pro daný problém poskytuje jemné seznámení s řadou základních konceptů algoritmů, jako je velká notace O , algoritmy rozděl a panuj , datové struktury, jako jsou hromady a binární stromy , randomizované algoritmy , nejlepší, nejhorší a průměrná analýza případů , kompromisy mezi časoprostorem a horní a dolní hranice .

Optimální třídění malých polí (s minimálním množstvím srovnání a swapů) nebo rychlé (tj. S přihlédnutím k detailům specifickým pro stroj) je stále otevřeným problémem výzkumu a řešení jsou známá pouze pro velmi malá pole (<20 prvků). Podobně optimální (podle různých definic) třídění na paralelním počítači je otevřeným výzkumným tématem.

Klasifikace

Algoritmy řazení lze klasifikovat podle:

• Výpočetní náročnost
  • Nejlepší, nejhorší a průměrné chování případů z hlediska velikosti seznamu. U typických algoritmů sériového řazení je dobré chování O ( n  log  n ), paralelní řazení v O (log ²  n ) a špatné chování je O ( n ² ). Ideální chování pro sériové řazení je O ( n ), ale v průměrném případě to není možné. Optimální paralelní třídění je O (log  n ).
  • Výměna za algoritmy „na místě“.
• Využití paměti (a využití dalších počítačových prostředků). Zejména některé třídicí algoritmy jsou „ na místě “. Striktně, na místě řazení vyžaduje pouze paměť O (1) mimo tříděné položky; někdy je O (log  n ) přídavná paměť považována za „na místě“.
• Rekurze: Některé algoritmy jsou buď rekurzivní, nebo nerekurzivní, zatímco jiné mohou být obojí (např. Sloučení).
• Stabilita: stabilní třídicí algoritmy udržují relativní pořadí záznamů se stejnými klíči (tj. Hodnotami).
• Bez ohledu na to, zda jsou srovnávacím druhem . Porovnávací řazení zkoumá data pouze porovnáním dvou prvků s operátorem porovnání.
• Obecná metoda: vkládání, výměna, výběr, sloučení atd. Směnné druhy zahrnují bublinové řazení a rychlé řazení. Výběrové řazení zahrnuje třídění cyklu a heapsort.
• Zda je algoritmus sériový nebo paralelní. Zbývající část této diskuse se téměř výhradně soustředí na sériové algoritmy a předpokládá sériovou operaci.
• Adaptabilita: Zda předčasnost vstupu ovlivňuje dobu běhu nebo ne. Algoritmy, které to berou v úvahu, jsou známy jako adaptivní .
• Online: Algoritmus, jako je Insertion Sort, který je online, může třídit konstantní proud vstupu.

Stabilita

Příklad stabilního řazení na hracích kartách. Když jsou karty tříděny podle pořadí se stabilním tříděním, musí dvě pětky zůstat ve stejném pořadí v seřazeném výstupu, ve kterém byly původně. Když jsou karty seřazeny nestabilním tříděním, pětky mohou skončit opačně pořadí v seřazeném výstupu.

Algoritmy stabilního řazení řadí stejné prvky ve stejném pořadí, v jakém se objevují na vstupu. Například v příkladu třídění karet napravo jsou karty seřazeny podle jejich hodnosti a jejich barva je ignorována. To umožňuje možnost více různých správně seřazených verzí původního seznamu. Algoritmy stabilního třídění zvolí jeden z nich podle následujícího pravidla: pokud se dvě položky porovnají jako stejné (jako dvě 5 karet), pak bude zachováno jejich relativní pořadí, tj. Pokud jedna přijde na vstup před druhou, přijde před druhým ve výstupu.

Stabilita je důležitá pro zachování pořádku ve více třídách ve stejné sadě dat . Řekněme například, že záznamy studentů sestávající z části názvu a sekce třídy jsou seřazeny dynamicky, nejprve podle jména, poté podle sekce třídy. Pokud je v obou případech použit stabilní třídící algoritmus, operace řazení podle třídy sekce nezmění pořadí názvů; u nestabilního řazení by mohlo dojít k tomu, že řazení podle sekcí zamíchá pořadí jmen, což má za následek neabecední seznam studentů.

Formálněji mohou být tříděná data reprezentována jako záznam nebo n -tice hodnot a ta část dat, která se používá k třídění, se nazývá klíč . V příkladu karty jsou karty reprezentovány jako rekord (hodnost, barva) a klíčem je hodnost. Algoritmus řazení je stabilní, pokud existují dva záznamy R a S se stejným klíčem a R se objeví před S v původním seznamu, pak se R vždy zobrazí před S v seřazeném seznamu.

Když jsou stejné prvky nerozeznatelné, například u celých čísel, nebo obecněji, u dat, kde je klíčem celý prvek, není stabilita problém. Stabilita také není problém, pokud jsou všechny klíče jiné.

Nestabilní třídicí algoritmy lze speciálně implementovat, aby byly stabilní. Jedním ze způsobů, jak toho dosáhnout, je uměle rozšířit porovnání klíčů, takže o porovnání mezi dvěma objekty s jinak stejnými klíči se rozhodne pomocí pořadí položek v původním vstupním seznamu jako tie-breakeru. Zapamatování této objednávky však může vyžadovat další čas a prostor.

Jedna aplikace pro stabilní algoritmy řazení je třídění seznamu pomocí primárního a sekundárního klíče. Předpokládejme například, že si přejeme roztřídit kombinaci karet tak, aby barvy byly v pořadí klubů (♣), diamantů ( ♦ ), srdcí ( ♥ ), rýčů (♠) a v každé barvě byly karty seřazeny podle hodnost. To lze provést nejprve seřazením karet podle hodnosti (pomocí jakéhokoli řazení) a poté stabilním seřazením podle barvy:

V rámci každé barvy zachovává stabilní řazení seřazení podle hodnosti, které již bylo provedeno. Tuto myšlenku lze rozšířit na libovolný počet klíčů a využívá ji radixové řazení . Stejného účinku lze dosáhnout nestabilním tříděním pomocí srovnání lexikografického klíče, které např. Nejprve porovnává podle barvy a poté porovnává podle pořadí, pokud jsou barvy shodné.

Porovnání algoritmů

V těchto tabulkách je n počet záznamů, které mají být tříděny. Sloupce „Nejlepší“, „Průměr“ a „Nejhorší“ udávají časovou složitost v každém případě za předpokladu, že délka každého klíče je konstantní, a tedy že všechna srovnání, swapy a další operace mohou probíhat v konstantním čase. „Paměť“ označuje množství dalšího úložného prostoru potřebného navíc k tomu, který používá samotný seznam, za stejného předpokladu. Uvedené doby běhu a požadavky na paměť jsou uvnitř velké notace O , na základně logaritmů tedy nezáleží. Záznamový protokol ² n znamená (log n ) ² .

Porovnávací druhy

Níže je tabulka typů srovnání . Porovnávací řazení nemůže v průměru fungovat lépe než O ( n log n ) .

Porovnávací druhy

název	Nejlepší	Průměrný	Nejhorší	Paměť	Stabilní	Metoda	Další poznámky
Rychlé řazení	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	${\ displaystyle \ log n}$	Ne	Rozdělení	Quicksort se obvykle provádí na místě s prostorem zásobníku O (log n ) .
Sloučit třídění	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ano	Sloučení	Vysoce paralelizovatelný (až O (log n ) pomocí Algoritmu tří Maďarů).
Sloučení na místě	-	-	${\ displaystyle n \ log ^{2} n}$	1	Ano	Sloučení	Lze implementovat jako stabilní třídění založené na stabilním slučování na místě.
Introsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle \ log n}$	Ne	Rozdělení a výběr	Používá se v několika implementacích STL .
Heapsort	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ne	Výběr
Třídění vložení	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ano	Vložení	O ( n + d ) , v nejhorším případě nad sekvencemi, které mají d inverze .
Blokové řazení	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ano	Vložení a sloučení	Zkombinujte algoritmus sloučení na místě založený na bloku s typem sloučení zdola nahoru . ${\ Displaystyle O (n)}$
Timsort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ano	Vložení a sloučení	Provádí porovnání n-1, když jsou data již seřazena nebo obrácena.
Výběrové řazení	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ne	Výběr	Stabilní s větším prostorem, při použití propojených seznamů nebo při provedení jako varianta řazení vložení místo prohození dvou položek. ${\ Displaystyle O (n)}$
Kostka	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ano	Vložení	Provádí porovnání n-1, když jsou data již seřazena nebo obrácena.
Shellsort	${\ displaystyle n \ log n}$	${\ displaystyle n^{4/3}}$	${\ displaystyle n^{3/2}}$	1	Ne	Vložení	Malá velikost kódu.
Bublinkové řazení	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ano	Výměna	Malá velikost kódu.
Směnit řazení	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ano	Výměna	Malá velikost kódu.
Třídění stromů	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$(vyrovnaný)	n	Ano	Vložení	Při použití binárního vyhledávacího stromu s vlastním vyvážením .
Cyklus řazení	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ne	Výběr	Na místě s teoreticky optimálním počtem zápisů.
Řazení knihovny	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	n	Ne	Vložení	Podobně jako při zařazování s mezerou. Vyžaduje náhodně permutující vstup, který zaručuje časové limity s vysokou pravděpodobností, což jej činí nestabilním.
Třídění trpělivosti	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ne	Vložení a výběr	Vyhledá všechny nejdéle rostoucí dílčí sekvence v O ( n log n ) .
Smoothsort	n	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	1	Ne	Výběr	Adaptivní varianta heapsort na základě sekvence Leonardo spíše než tradiční binární haldy .
Strand sort	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	n	Ano	Výběr
Druh turnaje	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	${\ displaystyle n \ log n}$	n	Ne	Výběr	Variace Heapsortu.
Druh koktejlové třepačky	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ano	Výměna	Varianta Bubblesortu, která dobře pracuje s malými hodnotami na konci seznamu
Hřebenové řazení	${\ displaystyle n \ log n}$	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ne	Výměna	V průměru rychlejší než bublinkové třídění.
Gnome sort	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ano	Výměna	Malá velikost kódu.
Zvláštní - dokonce i třídit	n	${\ displaystyle n^{2}}$	${\ displaystyle n^{2}}$	1	Ano	Výměna	Lze snadno spustit na paralelních procesorech.

Nesrovnatelné druhy

Následující tabulka popisuje algoritmy řazení celých čísel a další algoritmy řazení, které nejsou srovnávacími druhy . Jako takové nejsou omezeny na Ω ( n log n ) . Níže uvedené složitosti předpokládají n položek, které mají být tříděny, s klíči velikosti k , číslice d a r v rozsahu čísel, která mají být tříděna. Mnoho z nich je založeno na předpokladu, že velikost klíče je dostatečně velká, aby všechny položky měly jedinečné hodnoty klíčů, a tedy že n ≪ 2 ^k , kde ≪ znamená „mnohem méně než“. V modelu stroje s náhodným přístupem k jednotkovým nákladům algoritmy s dobou běhu , jako je radixové řazení, stále vyžadují čas úměrný Θ ( n log n ) , protože n je omezeno na ne více než a větší počet prvků třídění by vyžadovalo větší k , aby bylo možné je uložit do paměti. ${\ displaystyle \ scriptstyle n \ cdot {\ frac {k} {d}}}$${\ Displaystyle 2^{\ frac {k} {d}}}$

Nesrovnatelné druhy

název	Nejlepší	Průměrný	Nejhorší	Paměť	Stabilní	n ≪ 2 k	Poznámky
Druh holubí díry	-	${\ displaystyle n+2^{k}}$	${\ displaystyle n+2^{k}}$	${\ Displaystyle 2^{k}}$	Ano	Ano	Nelze řadit celá čísla.
Seřadit kbelík (jednotné klíče)	-	${\ displaystyle n+k}$	${\ Displaystyle n^{2} \ cdot k}$	${\ Displaystyle n \ cdot k}$	Ano	Ne	Předpokládá rovnoměrnou distribuci prvků z domény v poli. Nelze také řadit celá čísla
Seřadit kbelík (celočíselné klíče)	-	${\ displaystyle n+r}$	${\ displaystyle n+r}$	${\ displaystyle n+r}$	Ano	Ano	Pokud r je , pak průměrná časová složitost je . ${\ Displaystyle O (n)}$${\ Displaystyle O (n)}$
Počítání	-	${\ displaystyle n+r}$	${\ displaystyle n+r}$	${\ displaystyle n+r}$	Ano	Ano	Pokud r je , pak průměrná časová složitost je . ${\ Displaystyle O (n)}$${\ Displaystyle O (n)}$
LSD Radix Sort	${\ displaystyle n}$	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	Ano	Ne	${\ displaystyle {\ frac {k} {d}}}$úrovně rekurze, 2 d pro početní pole. Na rozdíl od většiny distribučních druhů to může třídit čísla s plovoucí desetinnou čárkou , záporná čísla a další.
Řazení MSD Radix	-	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	Ano	Ne	Stabilní verze používá externí pole velikosti n pro uložení všech přihrádek. Stejně jako varianta LSD může třídit celá čísla.
Řazení MSD Radix (na místě)	-	${\ Displaystyle n \ cdot {\ frac {k} {1}}}$	${\ Displaystyle n \ cdot {\ frac {k} {1}}}$	${\ displaystyle 2^{1}}$	Ne	Ne	d = 1 pro místní rekurzivní úrovně, žádné pole počtu. ${\ displaystyle k/1}$
Spreadsort	n	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ Displaystyle n \ cdot \ left ({{\ frac {k} {s}}+d} \ right)}$	${\ displaystyle {\ frac {k} {d}} \ cdot 2^{d}}$	Ne	Ne	Asymptotické jsou založeny na předpokladu, že n ≪ 2 k , ale algoritmus to nevyžaduje.
Burstsort	-	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	Ne	Ne	Má lepší konstantní faktor než třídění radixů pro řazení řetězců. Ačkoli se poněkud spoléhá na specifika běžně se vyskytujících řetězců.
Flashsort	n	${\ displaystyle n+r}$	${\ displaystyle n^{2}}$	n	Ne	Ne	Ke spuštění v lineárním čase vyžaduje rovnoměrné rozložení prvků z domény v poli. Pokud je distribuce extrémně zkosená, pak může jít kvadraticky, pokud je základní řazení kvadratické (obvykle se jedná o vkládací řazení). Místní verze není stabilní.
Pošťák	-	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ Displaystyle n \ cdot {\ frac {k} {d}}}$	${\ displaystyle n+2^{d}}$	-	Ne	Variace bucket sort, která funguje velmi podobně jako MSD Radix Sort. Specifické pro potřeby post služby.

Samplesort lze použít k paralelizaci jakéhokoli nesrovnávacího řazení efektivním rozdělením dat do několika segmentů a následným předáním třídění několika procesorům bez nutnosti sloučení, protože segmenty jsou již mezi sebou seřazeny.

Ostatní

Některé algoritmy jsou pomalé ve srovnání s algoritmy diskutovanými výše, například bogosort s neomezeným časem běhu a loutkovým druhem, který má čas běhu O ( n ^2,7 ). Tyto druhy jsou obvykle popsány pro vzdělávací účely, aby se ukázalo, jak se odhaduje doba běhu algoritmů. Následující tabulka popisuje některé algoritmy řazení, které jsou nepraktické pro použití v reálném prostředí v tradičních kontextech softwaru kvůli extrémně špatnému výkonu nebo specializovaným požadavkům na hardware.

název	Nejlepší	Průměrný	Nejhorší	Paměť	Stabilní	Srovnání	Další poznámky
Třídění korálků	n	S	S	${\ displaystyle n^{2}}$	N/A	Ne	Funguje pouze s kladnými celými čísly. Ke spuštění v garantovaném čase vyžaduje specializovaný hardware . Existuje možnost implementace softwaru, ale doba běhu bude , kde S je součet všech celých čísel, která mají být tříděna, v případě malých celých čísel to lze považovat za lineární. ${\ Displaystyle O (n)}$${\ displaystyle O (S)}$
Jednoduché třídění palačinek	-	n	n	${\ displaystyle \ log n}$	Ne	Ano	Count je počet otočení.
Třídění špaget (hlasování)	n	n	n	${\ displaystyle n^{2}}$	Ano	Polling	Toto je analogový algoritmus lineárního času pro třídění posloupnosti položek, který vyžaduje prostor zásobníku O ( n ), a řazení je stabilní. To vyžaduje n paralelních procesorů. Viz třídění špaget#Analýza .
Třídící síť	Liší se	Liší se	Liší se	Liší se	Liší se (stabilní třídicí sítě vyžadují více srovnání)	Ano	Pořadí srovnání je stanoveno předem na základě velikosti pevné sítě.
Bitonický třídič	${\ displaystyle \ log ^{2} n}$ paralelní	${\ displaystyle \ log ^{2} n}$ paralelní	${\ displaystyle n \ log ^{2} n}$ neparalelní	1	Ne	Ano	Efektivní variace třídicích sítí.
Bogosort	n	${\ displaystyle (n \ times n!)}$	neomezený (jistý), (očekávaný)${\ displaystyle (n \ times n!)}$	1	Ne	Ano	Náhodné míchání. Používá se pouze pro účely, protože i očekávaná nejlepší doba běhu je hrozná.
Třídění loutek	${\ displaystyle n^{\ log 3/\ log 1.5}}$	${\ displaystyle n^{\ log 3/\ log 1.5}}$	${\ displaystyle n^{\ log 3/\ log 1.5}}$	n	Ne	Ano	Pomalejší než většina třídicích algoritmů (i naivních) s časovou složitostí O ( n log 3 / log 1,5 ) = O ( n 2,7095 ... ) Může být stabilní a je také třídící sítí .
Zpomaluje	${\ displaystyle n^{\ log n}}$	${\ displaystyle n^{\ log n}}$	${\ displaystyle n^{\ log n}}$	n	Ne	Ano	Algoritmus znásobení a odevzdání, antonymní s algoritmem rozděl a panuj .

Teoretičtí počítačoví vědci podrobně popsali další algoritmy řazení, které poskytují lepší časovou složitost než O ( n log n ) za předpokladu dalších omezení, včetně:

• Thorupův algoritmus , randomizovaný algoritmus pro třídění klíčů z domény konečné velikosti, přičemž čas O ( n log log n ) zabírá čas a O ( n ) prostor.
• Randomizovaný algoritmus třídění celých čísel s očekávaným časem a prostorem O ( n ).${\ Displaystyle O \ left (n {\ sqrt {\ log \ log n}} \ right)}$

Populární algoritmy řazení

I když existuje velké množství třídicích algoritmů, v praktických implementacích převažuje několik algoritmů. Vkládací třídění je široce používáno pro malé datové sady, zatímco pro velké datové sady je používáno asymptoticky efektivní třídění, primárně heapsort, merge sort nebo quicksort. Efektivní implementace obecně používají hybridní algoritmus , který kombinuje asymptoticky účinný algoritmus pro celkové řazení s vkládáním pro malé seznamy v dolní části rekurze. Vysoce vyladěné implementace používají sofistikovanější varianty, jako je Timsort (sloučení, vložení a další logika), používané v Androidu, Javě a Pythonu a introsort (quicksort a heapsort), používané (ve variantních formách) v nějakém C ++ řazení implementací a v .NET.

Pro omezenější data, jako jsou čísla v pevném intervalu, se široce používají distribuční druhy, jako je počítání nebo radix. Třídění a varianty bublin se v praxi používají jen zřídka, ale běžně se vyskytují při výuce a teoretických diskusích.

Při fyzickém třídění předmětů (například podle abecedy papírů, testů nebo knih) lidé intuitivně obecně používají vkládání pro malé sady. U větších sad lidé často používají první segment, například podle počátečního písmene, a vícenásobné segmentování umožňuje praktické třídění velmi velkých sad. Prostor je často relativně levný, například rozložením předmětů na podlahu nebo na velkou plochu, ale operace jsou nákladné, zejména přesunutí objektu na velkou vzdálenost - důležitá je referenční lokalita . Sloučení jsou také praktické pro fyzické objekty, zejména proto, že lze použít dvě ruce, jednu pro každý seznam ke sloučení, zatímco jiné algoritmy, jako například heapsort nebo quicksort, jsou pro lidské použití špatně vhodné. Praktické pro fyzické použití jsou i další algoritmy, jako například knihovní třídění , varianta vkládacího třídění, které ponechává mezery.

Jednoduché druhy

Dva z nejjednodušších druhů jsou vkládání a výběr, oba jsou efektivní pro malá data, kvůli nízké režii, ale ne efektivní pro velká data. Vkládání je v praxi obecně rychlejší než výběrové řazení, kvůli menšímu počtu srovnání a dobrému výkonu na téměř tříděných datech, a proto je v praxi upřednostňováno, ale výběrové řazení používá méně zápisů, a proto se používá, když je výkon zápisu omezujícím faktorem.

Třídění vložení

Vkládací třídění je jednoduchý třídicí algoritmus, který je relativně účinný pro malé seznamy a většinou seřazené seznamy a často se používá jako součást sofistikovanějších algoritmů. Funguje to tak, že prvky ze seznamu vezmeme jeden po druhém a vložíme je na správném místě do nového seřazeného seznamu podobně, jako když vkládáme peníze do peněženky. V polích může nový seznam a zbývající prvky sdílet prostor pole, ale vložení je drahé a vyžaduje přesunutí všech následujících prvků o jeden. Shellsort (viz níže) je varianta vkládání, která je efektivnější pro větší seznamy.

Výběrové řazení

Třídění výběru je srovnání na místě . Má složitost O ( n ² ), takže je na velkých seznamech neefektivní a obecně funguje hůře než podobné vkládání . Selection sort je známý svou jednoduchostí a má také výkonnostní výhody oproti složitějším algoritmům v určitých situacích.

Algoritmus najde minimální hodnotu, zamění ji s hodnotou na první pozici a tyto kroky zopakuje pro zbytek seznamu. Neprovádí více než n swapů, a proto je užitečný tam, kde je swapování velmi nákladné.

Efektivní druhy

Praktické obecné třídící algoritmy jsou téměř vždy založeny na algoritmu s průměrnou časovou složitostí (a obecně nejhorší složitostí) O ( n log n ), z nichž nejběžnější jsou heapsort, merge sort a quicksort. Každý z nich má výhody a nevýhody, přičemž nejvýznamnější je, že jednoduchá implementace sloučení řazení využívá O ( n ) další prostor a jednoduchá implementace quicksortu má složitost nejhoršího případu O ( n ² ). Tyto problémy lze vyřešit nebo zlepšit za cenu složitějšího algoritmu.

Zatímco tyto algoritmy jsou na náhodných datech asymptoticky účinné, pro praktickou účinnost na datech z reálného světa se používají různé modifikace. Za prvé, režie těchto algoritmů se stává významnou u menších dat, takže se často používá hybridní algoritmus, který obvykle přechází na třídění vložení, jakmile jsou data dostatečně malá. Za druhé, algoritmy často fungují špatně na již seřazených datech nebo téměř tříděných datech-ty jsou běžné v datech z reálného světa a lze je řadit v čase O ( n ) pomocí vhodných algoritmů. Nakonec mohou být také nestabilní a stabilita je často svým způsobem žádoucí vlastnost. Proto se často používají sofistikovanější algoritmy, jako je Timsort (na základě sloučení) nebo introsort (na základě quicksortu, návrat k heapsortu).

Sloučit třídění

Sloučení řazení využívá výhody snadného sloučení již seřazených seznamů do nového seřazeného seznamu. Začíná porovnáním každých dvou prvků (tj. 1 s 2, poté 3 se 4 ...) a jejich záměnou, pokud by první měl přijít po druhém. Potom sloučí každý z výsledných seznamů dvou do seznamů čtyř, poté sloučí tyto seznamy čtyř atd.; až se nakonec dva seznamy spojí do konečného seřazeného seznamu. Z zde popsaných algoritmů je to první, který se dobře přizpůsobuje velmi velkým seznamům, protože jeho nejhorší doba běhu je O ( n log n ). Lze jej také snadno použít na seznamy, nejen na pole, protože vyžaduje pouze sekvenční přístup, nikoli náhodný přístup. Má však další O ( n ) prostorovou složitost a zahrnuje velký počet kopií v jednoduchých implementacích.

Sloučení řazení zaznamenalo relativně nedávný nárůst popularity praktických implementací, a to díky jeho použití v propracovaném algoritmu Timsort , který se používá pro standardní rutinu řazení v programovacích jazycích Python a Java (od JDK7 ). Samotné sloučení je mimo jiné standardní rutinou v Perlu a používá se v Javě minimálně od roku 2000 v JDK1.3 .

Heapsort

Heapsort je mnohem efektivnější verzí výběru . Funguje to také tak, že určíte největší (nebo nejmenší) prvek seznamu, umístíte jej na konec (nebo začátek) seznamu, poté pokračujete zbytkem seznamu, ale tento úkol splníte efektivně pomocí datové struktury zvané halda , speciální typ binárního stromu . Jakmile bude seznam dat vytvořen na hromadu, kořenový uzel bude zaručeně největším (nebo nejmenším) prvkem. Když je odebrána a umístěna na konec seznamu, halda se přeskupí, takže největší zbývající prvek se přesune do kořene. Pomocí haldy hledání dalšího největšího prvku zabere místo lineárního skenování místo O ( n ) čas O (log n ) jako při jednoduchém výběru. To umožňuje Heapsortu běžet v čase O ( n log n ) a to je také složitost nejhoršího případu.

Rychlé řazení

Quicksort je algoritmus rozděl a panuj, který se opírá o operaci oddílu : k rozdělení pole je vybrán prvek nazývaný pivot . Všechny prvky menší než pivot jsou přesunuty před něj a všechny větší prvky jsou přesunuty po něm. To lze provést efektivně v lineárním čase a na místě . Menší a větší dílčí seznamy jsou pak rekurzivně tříděny. To poskytuje průměrnou časovou složitost O ( n log n ) s nízkou režií, a proto je to oblíbený algoritmus. Efektivní implementace quicksortu (s dělením na místě) jsou obvykle nestabilní a poněkud složité, ale patří mezi nejrychlejší třídicí algoritmy v praxi. QuickSort je spolu se skromným využitím prostoru O (log n ) jedním z nejpopulárnějších algoritmů řazení a je k dispozici v mnoha standardních programovacích knihovnách.

Důležité upozornění na quicksort je, že jeho nejhorší výkon je O ( n ² ); zatímco toto je vzácné, v naivních implementacích (výběr prvního nebo posledního prvku jako pivot) k tomu dochází u tříděných dat, což je běžný případ. Nejsložitější otázkou rychlého řazení je tedy výběr dobrého prvku otáčení, protože důsledně špatná volba čepů může mít za následek výrazně pomalejší výkon O ( n ² ), ale dobrá volba čepů přináší výkon O ( n log n ), který je asymptoticky optimální . Pokud je například v každém kroku jako pivot zvolen medián, pak algoritmus funguje v O ( n  log  n ). Nalezení mediánu, například pomocí algoritmu výběru mediánu mediánů , je však operací O ( n ) na netříděných seznamech, a proto vyžaduje značné režijní náklady na třídění. V praxi téměř náhodný výběr náhodného čepu přináší výkon O ( n  log  n ).

Shellsort

Shellsort, odlišný od bublinového řazení v tom, že přesouvá prvky do mnoha výměnných pozic .

Shellsort byl vynalezen Donaldem Shellem v roce 1959. Vylepšuje se při vkládání přesunutím mimo pořadí prvků o více než jednu pozici najednou. Koncept Shellsortu spočívá v tom, že vkládání probíhá v čase, kde k je největší vzdálenost mezi dvěma nemístnými prvky. To znamená, že obecně fungují v O ( n ² ), ale u dat, která jsou většinou řazena, s pouze několika prvky mimo místo, fungují rychleji. Takže tím, že nejprve třídíte prvky daleko a postupně zmenšujete mezeru mezi prvky pro třídění, konečné řazení počítá mnohem rychleji. Jednu implementaci lze popsat jako uspořádání datové sekvence v dvourozměrném poli a následné řazení sloupců pole pomocí vkládání. ${\ displaystyle O (kn)}$

Časová složitost Shellsortu v nejhorším případě je otevřený problém a závisí na použité sekvenci mezer, přičemž známé složitosti se pohybují od O ( n ² ) do O ( n ^4/3 ) a Θ ( n log ² n ). To v kombinaci se skutečností, že Shellsort je na místě , potřebuje jen relativně malé množství kódu a nevyžaduje použití zásobníku hovorů , je užitečné v situacích, kdy je paměť mimořádně náročná , například ve vestavěných systémech a jádra operačního systému .

Třídění a varianty bublin

Bubble sort a varianty jako Shellsort a koktejlové řazení jsou jednoduché, vysoce neefektivní algoritmy řazení. Často se s nimi v úvodních textech setkáváme kvůli snadné analýze, ale v praxi se používají jen zřídka.

Bublinkové řazení

Řazení podle bublin, algoritmus řazení, který průběžně prochází seznamem, vyměňuje položky, dokud se nezobrazí ve správném pořadí.

Bubble sort je jednoduchý algoritmus řazení. Algoritmus začíná na začátku sady dat. Porovnává první dva prvky, a pokud je první větší než druhý, prohodí je. Pokračuje v tom pro každý pár sousedních prvků až do konce sady dat. Poté začíná znovu s prvními dvěma prvky a opakuje se, dokud při posledním průchodu nedojde k výměně. Průměrný čas a nejhorší výkon tohoto algoritmu je O ( n ² ), takže se zřídka používá k třídění velkých neuspořádaných datových sad. Bublinové třídění lze použít k třídění malého počtu položek (kde jeho asymptotická neúčinnost není vysoká pokuta). Řazení bublin lze také efektivně použít v seznamu libovolné délky, který je téměř tříděn (to znamená, že prvky nejsou výrazně mimo). Pokud například libovolný počet prvků není na místě pouze o jednu pozici (např. 0123546789 a 1032547698), výměna bublinových řazení je uvede do pořádku v prvním průchodu, druhý průchod najde všechny prvky v pořadí, takže řazení bude trvat jen 2 n času.

Hřebenové řazení

Comb sort je poměrně jednoduchý algoritmus řazení založený na třídění bublin a původně navržený Włodzimierzem Dobosiewiczem v roce 1980. Později byl znovu objeven a propagován Stephenem Laceym a Richardem Boxem s článkem Byte Magazine publikovaným v dubnu 1991. Základní myšlenkou je eliminovat želvy , nebo malé hodnoty na konci seznamu, protože v bublinovém třídění tyto zpomalují řazení. ( Králíci , velké hodnoty kolem začátku seznamu, nepředstavují problém při řazení bublin) Toho je dosaženo tím, že se v poli nejprve vymění prvky, které jsou od sebe v určité vzdálenosti, než že by se prvky vyměňovaly pouze v případě, že sousedí s navzájem a poté zmenšovat zvolenou vzdálenost, dokud nebude fungovat jako normální bublinové řazení. Pokud tedy lze Shellsort považovat za zobecněnou verzi vkládacího druhu, která prohodí prvky v určité vzdálenosti od sebe, lze hřebenové řazení považovat za stejné zobecnění aplikované na bublinové třídění.

Směnit řazení

Burzovní řazení je někdy zaměňováno s bublinovým tříděním, ačkoli algoritmy jsou ve skutečnosti odlišné. Výměna řazení funguje tak, že porovnává první prvek se všemi prvky nad ním a podle potřeby se prohodí, čímž zaručuje, že první prvek je správný pro konečné pořadí řazení; pak pokračuje stejným způsobem pro druhý prvek atd. Postrádá tu výhodu, kterou má bublinový druh detekce v jednom průchodu, pokud je seznam již seřazen, ale může být rychlejší než třídění bublin podle konstantního faktoru (o jeden průchod méně přes data, která mají být tříděna; o polovinu více celkových srovnání) v nejhorší situace. Jako každé jednoduché třídění O ( n ² ) může být přiměřeně rychlé přes velmi malé datové sady, i když obecně bude řazení vkládání rychlejší.

Distribuční třídění

Distribuční třídění se týká jakéhokoli algoritmu třídění, kde jsou data distribuována z jejich vstupu do více mezilehlých struktur, které jsou poté shromážděny a umístěny na výstup. Například bucket sort a flashsort jsou distribuční algoritmy založené na distribuci. Algoritmy třídění distribuce lze použít na jednom procesoru nebo mohou být distribuovaným algoritmem , kde jsou jednotlivé podmnožiny tříděny samostatně na různých procesorech a poté kombinovány. To umožňuje externí třídění dat příliš velké na to, aby se vešlo do paměti jednoho počítače.

Počítání

Třídění počítání je použitelné, když je známo, že každý vstup patří do konkrétní sady, S , možností. Algoritmus běží v O (| S | + n ) čase a O (| S |) paměti, kde n je délka vstupu. Funguje to tak, že vytvoříte celočíselné pole velikosti | S | a pomocí i th bin počítat výskyty i tého člena S na vstupu. Každý vstup je pak počítán zvýšením hodnoty jeho odpovídajícího zásobníku. Poté se pole počítání smyčkou pro uspořádání všech vstupů v pořadí. Tento třídicí algoritmus často nelze použít, protože S musí být přiměřeně malý, aby byl algoritmus účinný, ale je extrémně rychlý a vykazuje velké asymptotické chování, jak se zvyšuje n . Lze jej také upravit tak, aby poskytoval stabilní chování.

Kbelíkové řazení

Bucket sort je třídící a dobývací algoritmus třídění, který generalizuje počítání třídění rozdělením pole na konečný počet segmentů. Každý segment je pak tříděn jednotlivě, buď pomocí jiného třídicího algoritmu, nebo rekurzivně pomocí algoritmu třídění kbelíku.

Seřazení segmentu funguje nejlépe, když jsou prvky datové sady rovnoměrně rozloženy mezi všechny segmenty.

Radixové řazení

Radix sort je algoritmus, který třídí čísla zpracováním jednotlivých číslic. n čísel skládajících se z k číslic je seřazeno v čase O ( n · k ). Radix sort umí zpracovávat číslice každého čísla buď od nejméně významné číslice (LSD), nebo od nejvýznamnější číslice (MSD). Algoritmus LSD nejprve setřídí seznam podle nejméně významné číslice při zachování jejich relativního pořadí pomocí stabilního řazení. Poté je seřadí podle další číslice a tak dále od nejméně významných po nejvýznamnější a končí seřazeným seznamem. Zatímco radixové řazení LSD vyžaduje použití stabilního řazení, algoritmus radixového řazení MSD nikoli (pokud není požadováno stabilní třídění). Místní řazení radixů MSD není stabilní. Je běžné, že algoritmus počítání řazení je interně používán radixovým tříděním. Hybridní třídění přístup, jako je například použití vložení třídění malých zásobníků, zlepšuje výkonnost radix třídění významně.

Vzory využití paměti a třídění indexů

Když se velikost pole, které má být tříděno, blíží nebo překračuje dostupnou primární paměť, takže musí být použito (mnohem pomalejší) místo na disku nebo odkládacím prostoru, nabývá na významu způsob využití paměti třídicího algoritmu a algoritmus, který mohl být spravedlivě efektivní, když se pole snadno vejde do RAM, může být nepraktické. V tomto scénáři se celkový počet srovnání stává (relativně) méně důležitým a počet, kolikrát musí být části paměti zkopírovány nebo vyměněny na a z disku, může dominovat výkonnostním charakteristikám algoritmu. Počet průchodů a lokalizace srovnání tedy může být důležitější než hrubý počet srovnání, protože ke vzájemnému porovnávání blízkých prvků dochází při rychlosti systémové sběrnice (nebo při ukládání do mezipaměti dokonce při rychlosti procesoru ), což v porovnání na rychlost disku, je prakticky okamžitý.

Například populární rekurzivní algoritmus rychlého řazení poskytuje celkem rozumný výkon s adekvátní pamětí RAM, ale vzhledem k rekurzivnímu způsobu kopírování částí pole se stává mnohem méně praktickým, když se pole nevejde do paměti RAM, protože to může způsobit řadu pomalé kopírování nebo přesouvání operací na a z disku. V takovém případě může být vhodnější jiný algoritmus, i když vyžaduje více celkových srovnání.

Jedním ze způsobů, jak tento problém vyřešit, který funguje dobře, když jsou složité záznamy (například v relační databázi ) řazeny podle relativně malého klíčového pole, je vytvořit index do pole a poté třídit index, nikoli celý pole. (Vytříděnou verzi celého pole pak lze vytvořit jedním průchodem, čtením z indexu, ale často to ani není nutné, protože seřazený index je dostačující.) Protože je index mnohem menší než celé pole, může snadno se vejde do paměti, kam by se celé pole nevešlo, což účinně eliminuje problém s výměnou disku. Tento postup se někdy nazývá „třídění tagů“.

Další technikou pro překonání problému s velikostí paměti je použití externího třídění , například jedním ze způsobů je kombinovat dva algoritmy způsobem, který využívá sílu každého ke zlepšení celkového výkonu. Pole může být například rozděleno na bloky o velikosti, která se vejde do paměti RAM, obsah každého bloku je seřazen pomocí účinného algoritmu (například quicksort ) a výsledky sloučeny pomocí k -way sloučení podobného tomu, který byl použit v sloučit řazení . To je rychlejší než provádět sloučení nebo rychlé řazení v celém seznamu.

Techniky lze také kombinovat. Pro třídění velmi velkých souborů dat, které výrazně přesahují systémovou paměť, může být dokonce nutné index třídit pomocí algoritmu nebo kombinace algoritmů navržených tak, aby přiměřeně fungovaly s virtuální pamětí , tj. Aby se snížilo množství požadovaného odkládání.

Související algoritmy

Související problémy zahrnují částečné třídění (třídění pouze k nejmenších prvků seznamu nebo alternativně počítání k nejmenších prvků, ale neuspořádaných) a výběr (výpočet k tého nejmenšího prvku). Ty lze neefektivně vyřešit celkovým tříděním, ale existují účinnější algoritmy, často odvozené zobecněním algoritmu řazení. Nejpozoruhodnějším příkladem je quickselect , který souvisí s quicksortem . Naopak některé algoritmy řazení lze odvodit opakovanou aplikací selekčního algoritmu; quicksort a quickselect lze vnímat jako stejný otočný pohyb, liší se pouze v tom, zda se opakuje na obou stranách (quicksort, dělení a dobývání ) nebo na jedné straně (quickselect, snížit a dobýt ).

Nějakým opakem algoritmu řazení je algoritmus míchání . Ty se zásadně liší, protože vyžadují zdroj náhodných čísel. Shuffling lze také implementovat pomocí třídicího algoritmu, jmenovitě náhodným tříděním: přiřazení náhodného čísla každému prvku seznamu a následné řazení na základě náhodných čísel. To se však v praxi obecně nedělá a existuje dobře známý jednoduchý a účinný algoritmus pro míchání: Fisher-Yatesův náhodný výběr .

Viz také

• Kolace  - Montáž písemných informací do standardní pořadí
• Schwartzova transformace
• Algoritmus vyhledávání  - jakýkoli algoritmus, který řeší problém s vyhledáváním
• Kvantové řazení  - Algoritmy řazení pro kvantové počítače

Reference

Další čtení

• Knuth, Donald E. (1998), Sorting and Searching , The Art of Computer Programming, 3 (2nd ed.), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), „Efficient Sorting by Computer: An Introduction“, Computational Probability , New York: Academic Press, s.  101–130 , ISBN 0-12-394680-8

externí odkazy

• Řazení animací algoritmu na Wayback Machine (archivováno 3. března 2015).
• Sekvenční a paralelní algoritmy řazení - vysvětlení a analýzy mnoha algoritmů řazení.
• Slovník algoritmů, datové struktury a problémy - slovník algoritmů, technik, běžných funkcí a problémů.
• Mírně skeptický pohled na algoritmy řazení - diskutuje o několika klasických algoritmech a propaguje alternativy k algoritmu quicksort .
• 15 třídicích algoritmů za 6 minut (Youtube) - vizualizace a „audibilizace“ 15 třídicích algoritmů za 6 minut.
• Sekvence A036604 v databázi OEIS s názvem „Třídění čísel: minimální počet srovnání potřebných k seřazení n prvků“ - Provádí algoritmus Ford – Johnson .
• Algoritmy řazení používané na slavných obrazech (Youtube) - Vizualizace algoritmů řazení na mnoha slavných obrazech.
• Porovnání algoritmů řazení - Spustí sérii testů 9 hlavních algoritmů řazení pomocí Python timeit a Google Colab.