Algoritmus řazení - Sorting algorithm

v počítačová věda, a třídicí algoritmus je algoritmus který dává prvky a seznam v jistém objednat. Nejčastěji používané objednávky jsou číselné pořadí a lexikografický řád. Účinný třídění je důležité pro optimalizaci účinnost dalších algoritmů (např Vyhledávání a spojit algoritmy), které vyžadují, aby byla vstupní data v seřazených seznamech. Řazení je také často užitečné pro kanonizace dat a pro produkci výstupu čitelného člověkem. Formálněji musí výstup libovolného třídicího algoritmu splňovat dvě podmínky:

1. Výstup je v neklesajícím pořadí (každý prvek není menší než předchozí prvek podle požadovaného celková objednávka );
2. Výstupem je a permutace (přeskupení, ale zachující všechny původní prvky) vstupu.

Dále jsou vstupní data často uložena v pole, což dovoluje náhodný přístup, spíše než seznam, který pouze umožňuje sekvenční přístup; i když po vhodné úpravě lze na každý typ dat použít mnoho algoritmů.

Algoritmy řazení se často označují jako slovo následované slovem „sort“ a gramaticky se v angličtině používají jako fráze podstatného jména, například ve větě „je neefektivní používat třídění vložením na velkých seznamech“ fráze třídění vložení Odkazuje na třídění vložení třídicí algoritmus.

Dějiny

Od začátku práce na počítači přitahoval problém třídění velké množství výzkumu, snad kvůli složitosti jeho efektivního řešení navzdory jeho jednoduchému a známému tvrzení. Mezi autory algoritmů raného třídění bylo kolem roku 1951 Betty Holberton (nar Snyder), který pracoval ENIAC a UNIVAC.^[1][2] Třídění bublin byla analyzována již v roce 1956.^[3] Algoritmy srovnávacího třídění mají základní požadavek Ω (n log n) srovná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ání, jako např počítání řazení, může mít lepší výkon. Asymptoticky optimální algoritmy jsou známy od poloviny 20. století - užitečné nové algoritmy se stále vymýšlejí a nyní se široce používají Timsort datování do roku 2002 a třídění knihovny byl poprvé publikován v roce 2006.

V úvodu převažují třídicí algoritmy počítačová věda třídy, kde hojnost algoritmů pro daný problém poskytuje jemný úvod do různých konceptů základních algoritmů, jako je velká O notace, algoritmy rozděl a panuj, datové struktury jako hromady a binární stromy, randomizované algoritmy, nejlepší, nejhorší a průměrný případ analýza, časoprostorové kompromisy, a horní a dolní mez.

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

Klasifikace

Algoritmy řazení jsou často klasifikovány podle:

• Výpočetní složitost (nejhorší, průměrný a nejlepší chování) z hlediska velikosti seznamu (n). Pro typické algoritmy sériového třídění je dobré chování O (n logn), s paralelním tříděním v O (log² n) a špatné chování je O (n²). (Vidět Velká O notace.) 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 (logn). Porovnávací algoritmy řazení potřebujete alespoň Ω (n logn) srovnání pro většinu vstupů.
• Výpočetní složitost swapů (pro algoritmy „na místě“).
• Paměť využití (a využití dalších počítačových zdrojů). Některé třídicí algoritmy jsou zejména „na místě ". Přísně platí, že místní řazení vyžaduje kromě tříděných položek pouze O (1) paměť; někdy O (log (n)) další paměť je považována za „na místě“.
• Rekurze. Některé algoritmy jsou buď rekurzivní, nebo nerekurzivní, zatímco jiné mohou být oba (např. Sloučení).
• Stabilita: stabilní třídicí algoritmy udržovat relativní pořadí záznamů se stejnými klíči (tj. hodnotami).
• Ať už jsou nebo nejsou porovnání řazení. Porovnávací řazení zkoumá data pouze porovnáním dvou prvků s operátorem porovnání.
• Obecná metoda: vložení, výměna, výběr, sloučení, atd. Mezi burzy patří třídění podle bublin a rychlé třídění. Mezi druhy výběru patří shaker sort a heapsort.
• Zda je algoritmus sériový nebo paralelní. Zbytek této diskuse se téměř výlučně soustředí na sériové algoritmy a předpokládá sériovou operaci.
• Přizpůsobivost: To, zda předem nastavená hodnota vstupu ovlivňuje dobu běhu či nikoli. Algoritmy, které to berou v úvahu, jsou známy adaptivní.

Stabilita

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

Stabilní algoritmy řazení třídí opakované prvky ve stejném pořadí, v jakém se objevují na vstupu. Při třídění některých druhů dat se při určování pořadí řazení zkoumá pouze část dat. Například v příkladu třídění karet napravo jsou karty tříděny podle jejich pořadí a jejich barvy jsou ignorovány. To umožňuje možnost několika různých správně seřazených verzí původního seznamu. Stabilní třídicí algoritmy zvolí jeden z nich podle následujícího pravidla: pokud se dvě položky srovnají stejně, jako dvě karty 5, pak se jejich relativní pořadí zachová, takže pokud jedna na vstupu bude před druhou, bude také přijít před druhou ve výstupu.

Stabilita je důležitá z následujícího důvodu: řekněme, že záznamy studentů skládající se z části názvu a třídy jsou dynamicky tříděny na webové stránce, nejprve podle jména, poté podle sekce v druhé operaci. Pokud se v obou případech použije stabilní třídicí algoritmus, operace řazení podle tříd nezmění pořadí názvů; při nestabilním řazení by mohlo dojít k tomu, že řazení podle sekcí zamíchá pořadí jmen. Pomocí stabilního řazení si uživatelé mohou vybrat řazení podle sekce a poté podle názvu, nejprve seřazení podle názvu a potom opět řazení podle sekce, což má za následek zachování pořadí názvů. (Některé tabulkové programy toto chování dodržují: řazení podle názvu a poté podle oddílů poskytuje abecední seznam studentů podle oddílů.)

Formálněji lze třídená data představovat jako záznam nebo n-tici hodnot a část dat, která se používá pro třídění, se nazývá klíč. V příkladu karty jsou karty reprezentovány jako záznam (hodnost, barva) a klíčem je hodnost. Algoritmus řazení je stabilní, pokud vždy 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 R se vždy objeví před S v seřazeném seznamu.

Pokud jsou stejné prvky nerozeznatelné, například s celými čísly nebo obecněji, všechna data, kde je klíčem celý prvek, není problém stabilita. Stabilita také není problém, pokud jsou všechny klíče odlišné.

Nestabilní třídicí algoritmy lze speciálně implementovat tak, 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 rozhoduje pomocí pořadí položek v původním vstupním seznamu jako rozdělovač tie. Pamatování této objednávky však může vyžadovat více času a prostoru.

Jednou aplikací pro stabilní třídicí algoritmy je třídění seznamu pomocí primárního a sekundárního klíče. Předpokládejme například, že chceme roztřídit ruku karet tak, aby barvy byly v pořadí kluby (♣), diamanty (♦), srdce (♥), piky (♠) a v každé barvě jsou karty seřazeny podle hodnosti. Toho lze dosáhnout tak, že nejprve roztřídíte karty podle pořadí (pomocí jakéhokoli druhu) a poté provedete stabilní třídění podle barvy:

V každém obleku stabilní druh zachovává seřazení podle hodností, které již bylo provedeno. Tuto myšlenku lze rozšířit na libovolný počet klíčů a využívá ji radix sort. Stejného efektu lze dosáhnout při nestabilním řazení pomocí lexikografického srovnání klíčů, které např. Nejprve srovnává podle barvy, a poté porovnává podle hodnosti, pokud jsou barvy stejné.

Porovnání algoritmů

V této tabulce n je počet záznamů, které mají být tříděny. Sloupce „Průměr“ a „Nejhorší“ udávají časová složitost v každém případě za předpokladu, že délka každého klíče je konstantní, a že proto všechna srovnání, swapy a další potřebné operace mohou probíhat v konstantním čase. „Paměť“ označuje množství pomocného úložiště potřebného nad rámec toho, který používá samotný seznam, za stejného předpokladu. Doby běhu a požadavky na paměť uvedené níže je třeba chápat jako uvnitř velká O notace, proto základ logaritmů nezáleží; zápis log² n prostředek (log n)².

Druhy srovnání

Níže je tabulka druhy porovnání. Porovnávací druh nemůže fungovat lépe než Ó(n log n).^[4]

Druhy srovnání

název	Nejlepší	Průměrný	Nejhorší	Paměť	Stabilní	Metoda	Další poznámky
Quicksort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle n ^ {2}}$	${displaystyle log n}$	Ne	Rozdělení na oddíly	Quicksort se obvykle provádí na místě pomocí Ó(log n) prostor zásobníku.[5][6]
Sloučit třídění	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Ano	Sloučení	Vysoce paralelizovatelné (až do Ó(log n) pomocí Algoritmu tří Maďarů).[7]
Třídění sloučení na místě	—	—	${displaystyle nlog ^ {2} n}$	1	Ano	Sloučení	Lze implementovat jako stabilní řazení založené na stabilním slučování na místě.[8]
Introsort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle log n}$	Ne	Rozdělení a výběr	Používá se v několika STL implementace.
Heapsort	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	1	Ne	Výběr
Třídění vložení	n	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	1	Ano	Vložení	Ó(n + d), v nejhorším případě nad sekvencemi, které mají d inverze.
Blokovat řazení	n	${displaystyle nlog n}$	${displaystyle nlog n}$	1	Ano	Vkládání a slučování	Zkombinujte blok na bázi ${displaystyle O (n)}$ algoritmus slučování na místě[9] s sloučit řazení zdola nahoru.
Čtyřkolka	n	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Ano	Sloučení	Používá 4 vstupy třídicí síť.[10]
Timsort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Ano	Vkládání a slučování	Dělá n srovnání, když jsou data již tříděna nebo obrácena.
Třídění výběru	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	1	Ne	Výběr	Stabilní s ${displaystyle O (n)}$ více místa nebo při použití propojených seznamů.[11]
Cubesort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	n	Ano	Vložení	Dělá n srovnání, když jsou data již tříděna nebo obrácena.
Shellsort	${displaystyle nlog n}$	${displaystyle n ^ {4/3}}$	${displaystyle n ^ {3/2}}$	1	Ne	Vložení	Malá velikost kódu.
Třídění bublin	n	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	1	Ano	Výměna	Malá velikost kódu.
Třídění stromů	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$(vyrovnaný)	n	Ano	Vložení	Při použití a samovyvažující binární vyhledávací strom.
Třídění cyklů	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	1	Ne	Vložení	Na místě s teoreticky optimálním počtem zápisů.
Třídění knihovny	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle n ^ {2}}$	n	Ne	Vložení	Podobně jako u typu vložení s mezerou. Vyžaduje náhodné permutování vstupu, aby bylo zaručeno časové omezení s vysokou pravděpodobností, díky čemuž není stabilní.
Třídění trpělivosti	n	—	${displaystyle nlog n}$	n	Ne	Vkládání a výběr	Najde všechny nejdelší rostoucí subsekvence v Ó(n log n).
Smoothsort	n	${displaystyle nlog n}$	${displaystyle nlog n}$	1	Ne	Výběr	An adaptivní varianta haldy na základě Leonardova sekvence spíše než tradiční binární hromada.
Pramenové třídění	n	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	n	Ano	Výběr
Třídění turnajů	${displaystyle nlog n}$	${displaystyle nlog n}$	${displaystyle nlog n}$	n[12]	Ne	Výběr	Varianta třídění haldy.
Koktejl třepačka druh	n	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	1	Ano	Výměna	Varianta Bubblesort, která na konci seznamu dobře pracuje s malými hodnotami
Hřeben třídění	${displaystyle nlog 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.
Zrušit náhodné řazení[13]	n	kn	kn	n	Ne	Distribuce a sloučení	Neprovádějí se žádné výměny. Parametr k je úměrná entropii na vstupu. k = 1 pro objednaný nebo obráceně seřazený vstup.
Franceschiniho metoda[14]	—	${displaystyle nlog n}$	${displaystyle nlog n}$	1	Ano	?	Vystupuje Ó(n) datové pohyby.
Liché - sudé třídění	n	${displaystyle n ^ {2}}$	${displaystyle n ^ {2}}$	1	Ano	Výměna	Lze jej snadno spustit na paralelních procesorech.

Nesrovnávací druhy

Následující tabulka popisuje celočíselné třídění algoritmy a další třídicí algoritmy, které nejsou druhy porovnání. Jako takové se neomezují pouze na Ω(n log n).^[15] Složitosti níže předpokládají n položky, které mají být tříděny, s klíči velikosti k, velikost číslice d, a r rozsah čí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íče, a proto n ≪ 2^k, kde ≪ znamená „mnohem méně než“. V jednotkové ceně stroj s náhodným přístupem model, algoritmy s dobou chodu ${displaystyle scriptstyle ncdot {frac {k} {d}}}$, jako je radix sort, stále trvá čas úměrný Θ (n log n), protože n omezeno na maximálně ${displaystyle 2 ^ {frac {k} {d}}}$a větší počet prvků k třídění by vyžadoval větší k za účelem jejich uložení do paměti.^[16]

Nesrovnávací druhy

název	Nejlepší	Průměrný	Nejhorší	Paměť	Stabilní	n ≪ 2k	Poznámky
Pigeonhole druh	—	${displaystyle n + 2 ^ {k}}$	${displaystyle n + 2 ^ {k}}$	${displaystyle 2 ^ {k}}$	Ano	Ano
Třídění kbelíku (jednotné klíče)	—	${displaystyle n + k}$	${displaystyle n ^ {2} cdot k}$	${displaystyle ncdot k}$	Ano	Ne	Předpokládá jednotné rozdělení prvků z domény v poli.[17]
Třídění kbelíku (celočíselné klíče)	—	${displaystyle n + r}$	${displaystyle n + r}$	${displaystyle n + r}$	Ano	Ano	Li r je ${displaystyle O (n)}$, pak je průměrná časová složitost ${displaystyle O (n)}$.[18]
Počítání řazení	—	${displaystyle n + r}$	${displaystyle n + r}$	${displaystyle n + r}$	Ano	Ano	Li r je ${displaystyle O (n)}$, pak je průměrná časová složitost ${displaystyle O (n)}$.[17]
LSD Radix Sort	—	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle n + 2 ^ {d}}$	Ano	Ne	${displaystyle {frac {k} {d}}}$ úrovně rekurze, 2d pro počet pole.[17][18]
MSD Radix Sort	—	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle n + 2 ^ {d}}$	Ano	Ne	Stabilní verze používá externí pole velikosti n držet všechny koše.
MSD Radix Sort (na místě)	—	${displaystyle ncdot {frac {k} {1}}}$	${displaystyle ncdot {frac {k} {1}}}$	${displaystyle 2 ^ {1}}$	Ne	Ne	d = 1 pro na místě, ${displaystyle k / 1}$ úrovně rekurze, žádné pole počtu.
Spreadsort	n	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle ncdot left ({{frac {k} {s}} + d} ight)}$	${displaystyle {frac {k} {d}} cdot 2 ^ {d}}$	Ne	Ne	Asymptotické jsou založeny na předpokladu, že n ≪ 2k, ale algoritmus to nevyžaduje.
Burstsort	—	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle ncdot {frac {k} {d}}}$	Ne	Ne	Má lepší konstantní faktor než radix třídění pro třídění řetězců. Ačkoli se trochu spoléhá na specifika běžně se vyskytujících řetězců.
Flashsort	n	${displaystyle n + r}$	${displaystyle n ^ {2}}$	n	Ne	Ne	Vyžaduje jednotné rozdělení prvků z domény v poli, aby běželo v lineárním čase. Pokud je distribuce extrémně zkosená, může jít kvadraticky, pokud je základní řazení kvadratické (obvykle jde o třídění vložením). Místní verze není stabilní.
Pošťák třídí	—	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle ncdot {frac {k} {d}}}$	${displaystyle n + 2 ^ {d}}$	—	Ne	Varianta třídění lopaty, která funguje velmi podobně jako MSD Radix Sort. Specifické pro potřeby poštovních služeb.

Sampleort lze použít k paralelizaci kteréhokoli z nesrovnávacích druhů, a to efektivním rozdělením dat do několika segmentů a následným předáním řazení několika procesorům, bez nutnosti sloučení, protože segmenty jsou již tříděny mezi sebou.

Ostatní

Některé algoritmy jsou pomalé ve srovnání s algoritmy diskutovanými výše, například Bogosort s neomezenou dobou běhu a loutka třídění který má Ó(n^2.7) doba běhu. Tyto druhy jsou obvykle popsány pro vzdělávací účely, aby se prokázalo, jak se odhaduje doba chodu algoritmů. Následující tabulka popisuje některé algoritmy řazení, které jsou nepraktické pro použití v reálném životě v tradičních softwarových kontextech kvůli extrémně špatnému výkonu nebo specializovaným hardwarovým požadavkům.

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. Vyžaduje specializovaný hardware, aby mohl běžet zaručeně ${displaystyle O (n)}$ čas. Existuje možnost implementace softwaru, ale doba provozu bude ${displaystyle O (S)}$, 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í.
Jednoduché třídění palačinek	—	n	n	${displaystyle log n}$	Ne	Ano	Count je počet otočení.
Třídit špagety	n	n	n	${displaystyle n ^ {2}}$	Ano	Anketa	Toto je analogový algoritmus lineárního času pro třídění posloupnosti položek, který vyžaduje Ó(n) místo v zásobníku a řazení je stabilní. To vyžaduje n paralelní procesory. Vidět analýza špaget.
Třídění sítě	${displaystyle log ^ {2} n}$	${displaystyle log ^ {2} n}$	${displaystyle log ^ {2} n}$	${displaystyle nlog ^ {2} n}$	Liší se (stabilní třídicí sítě vyžadují více srovnání)	Ano	Pořadí porovnání je předem stanoveno na základě velikosti pevné sítě. Nepraktické pro více než 32 položek.[sporný – diskutovat]
Bitonický třídič	${displaystyle log ^ {2} n}$	${displaystyle log ^ {2} n}$	${displaystyle log ^ {2} n}$	${displaystyle nlog ^ {2} n}$	Ne	Ano	Efektivní variace třídících sítí.
Bogosort	n	${displaystyle (n imes n!)}$	neomezeně (jistě), ${displaystyle (n imes n!)}$ (očekávaný)	1	Ne	Ano	Náhodné míchání. Používá se pouze pro účely, protože i očekávaná doba běhu v nejlepším případě je hrozná.[19]
Stooge třídění	${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í Ó(nlog 3 / log 1.5 ) = Ó(n2.7095...).

Teoretičtí počítačoví vědci podrobně popsali další třídicí algoritmy, které poskytují lepší než Ó(n log n) časová složitost 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ž Ó(n log log n) čas a Ó(n) prostor.^[20]
• Náhodně celočíselné třídění přijímání algoritmů ${displaystyle Oleft (n {sqrt {log log n}} vpravo)}$ očekávaný čas a Ó(n) prostor.^[21]

Populární třídicí algoritmy

I když existuje velké množství třídicích algoritmů, v praktických implementacích převládá několik algoritmů. Třídění vložení je široce používáno pro malé datové sady, zatímco pro velké datové sady se používá asymptoticky efektivní řazení, primárně třídění haldy, sloučení nebo rychlé řazení. Efektivní implementace obecně používají a hybridní algoritmus kombinující asymptoticky efektivní algoritmus pro celkové řazení s vložením pro malé seznamy v dolní části rekurze. Vysoce vyladěné implementace používají sofistikovanější varianty, jako např Timsort (sloučení, vložení a další logika), používané v systémech Android, Java a Python a introsort (quicksort a heap sort), použitý (ve variantních formách) v některých C ++ řazení implementace a v .NET.

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

Při fyzickém třídění předmětů (jako jsou abecední řazení papírů, testů nebo knih) lidé intuitivně obecně používají druhy vkládání pro malé sady. U větších sérií lidé často nejprve kbelík, například počátečním písmenem, a vícenásobné bucková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 drahé, zejména přemístění předmětu na velkou vzdálenost - důležitá je referenční poloha. Sloučení sloučení je 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 je hromadné třídění nebo rychlé třídění, jsou špatně vhodné pro lidské použití. Jiné algoritmy, jako např třídění knihovny, varianta druhu vložení, která ponechává mezery, jsou také praktické pro fyzické použití.

Jednoduché druhy

Dva z nejjednodušších druhů jsou třídění vložením a výběrem, oba jsou efektivní pro malá data kvůli nízké režii, ale ne efektivní pro velká data. Řazení vložení je v praxi obecně rychlejší než řazení výběru, kvůli menšímu počtu srovnání a dobrému výkonu u téměř seřazených dat, a proto je v praxi upřednostňováno, ale řazení ř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í

Třídění vložení je jednoduchý třídicí algoritmus, který je relativně efektivní pro malé seznamy a většinou seřazené seznamy a často se používá jako součást složitějších algoritmů. Funguje to tak, že po jednom vezmete prvky ze seznamu a vložíte je do správné polohy do nového seřazeného seznamu, podobně jako jsme vložili peníze do naší peněženky.^[22] 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řesun všech následujících prvků o jeden. Shellsort (viz níže) je varianta druhu vložení, která je efektivnější pro větší seznamy.

Třídění výběru

Třídění výběru je na místě porovnání řazení. Má to Ó (n²), což je na velkých seznamech neefektivní a obecně má horší výsledky než podobné třídění vložení. Třídění výběru je známé svou jednoduchostí a v určitých situacích má také výkonnostní výhody oproti složitějším algoritmům.

Algoritmus najde minimální hodnotu, zamění ji s hodnotou na první pozici a tyto kroky opakuje pro zbytek seznamu.^[23] Nedělá to víc než n swapy, a je tedy užitečný tam, kde je swap velmi drahý.

Efektivní druhy

Praktické obecné třídicí 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 hromadné třídění, hromadné sloučení a rychlé řazení. Každá z nich má výhody a nevýhody, přičemž nejvýznamnější je to, že jednoduchá implementace sloučeného řazení používá O (n) další prostor a jednoduchá implementace rychlého řazení má O (n²) nejhorší složitost. Tyto problémy lze vyřešit nebo zlepšit za cenu složitějšího algoritmu.

Zatímco tyto algoritmy jsou asymptoticky účinné na náhodných datech, pro praktickou účinnost na datech v reálném světě se používají různé modifikace. Nejprve se režie těchto algoritmů stává významnou pro menší data, takže se často používá hybridní algoritmus, který se běžně přepne na druh vložení, jakmile jsou data dostatečně malá. Zadruhé, algoritmy často špatně fungují na již seřazených datech nebo na téměř seřazených datech - ty jsou běžné v reálných datech a lze je třídit v O (n) čas příslušnými algoritmy. Konečně mohou být také nestabilní a stabilita je často žádoucí vlastností. Často se tedy používají sofistikovanější algoritmy, jako např Timsort (na základě sloučení) nebo introsort (na základě quicksortu, spadnutí zpět na třídění haldy).

Sloučit třídění

Sloučit třídění využívá snadnosti sloučení již seřazených seznamů do nového seřazeného seznamu. Začíná to porovnáním každých dvou prvků (tj. 1 s 2, poté 3 se 4 ...) a jejich vý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.; dokud nejsou poslední dva seznamy sloučeny do konečného seřazeného seznamu.^[24] 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). Rovněž se snadno aplikuje 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) prostorová složitost a zahrnuje velké množství kopií v jednoduchých implementacích.

Sloučení druhu zaznamenalo relativně nedávný nárůst popularity praktických implementací díky jeho použití v sofistikovaném algoritmu Timsort, který se používá pro rutinu standardního třídění v programovacích jazycích Krajta^[25] a Jáva (do JDK7^[26]). Samotné sloučení je standardní rutina Perl,^[27] mimo jiné a v Javě se používá minimálně od roku 2000 v JDK1.3.^[28]

Heapsort

Heapsort je mnohem efektivnější verze výběr řazení. Funguje také tak, že určuje největší (nebo nejmenší) prvek seznamu, umístí jej na konec (nebo začátek) seznamu a poté pokračuje se zbytkem seznamu, ale efektivně splní tento úkol pomocí datové struktury zvané a halda, speciální typ binární strom.^[29] Jakmile se ze seznamu dat vytvoří halda, je zaručeno, že kořenový uzel bude největším (nebo nejmenším) prvkem. Když je odstraněna a umístěna na konec seznamu, hromada se přeskupí, takže největší zbývající prvek se přesune do kořenového adresáře. Použití haldy, nalezení dalšího největšího prvku trvá O (log n) čas namísto O (n) pro lineární skenování jako v jednoduchém výběru. To umožňuje Heapsortu běžet v O (n log n) času, a to je také nejhorší případ složitosti.

Quicksort

Quicksort je algoritmus rozděl a panuj který se spoléhá na a rozdělit operace: rozdělit pole, prvek zvaný a pivot je vybrána.^[30][31] Všechny prvky menší než pivot jsou přesunuty před ním a všechny větší prvky po něm. Toho lze dosáhnout efektivně v lineárním čase a na místě. Menší a větší podlisty jsou poté rekurzivně tříděny. Tím se získá průměrná časová složitost O (n log n), s nízkou režií, a jedná se tedy o populární algoritmus. Efektivní implementace quicksortu (s dělením na místě) jsou obvykle nestabilní druhy a poněkud složité, ale v praxi patří k nejrychlejším algoritmům třídění. Spolu s jeho skromným O (log n) využití prostoru, quicksort je jedním z nejpopulárnějších třídicích algoritmů a je k dispozici v mnoha standardních programovacích knihovnách.

Důležitým upozorněním 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 pivotního) k tomu dochází u tříděných dat, což je běžný případ. Nejsložitější otázkou v quicksortu je tedy volba dobrého otočného prvku, protože důsledně špatná volba otočných čepů může mít za následek drasticky pomalejší O (n²) výkon, ale dobrá volba čepů přináší O (n log n) výkon, který je asymptoticky optimální. Například pokud v každém kroku medián je vybrán jako pivot, pak algoritmus pracuje v O (n logn). Hledání mediánu, například pomocí medián mediánů algoritmus výběru je však O (n) operace na netříděných seznamech, a proto při třídění vyžaduje značné režijní náklady. V praxi výběr náhodného čepu téměř jistě přináší O (n logn) výkon.

Shellsort

Třídění Shell, odlišné od bublin, v tom, že přesouvá prvky do mnoha zaměnit pozice.

Shellsort byl vynalezen Donald Shell v roce 1959.^[32] Vylepšuje se při třídění vložením přesunutím mimo pořadí prvků více než jednu pozici najednou. Koncept za Shellsortem spočívá v tom, že v něm probíhá řazení ${displaystyle O (kn)}$ čas, kde k je největší vzdálenost mezi dvěma nemístními prvky. To znamená, že obecně vystupují v Ó(n²), ale u dat, která jsou většinou tříděna a mají jen několik prvků na místě, fungují rychleji. Takže tím, že nejprve seřadíte prvky daleko a postupně zmenšíte mezeru mezi prvky, které se mají seřadit, se konečné řazení počítá mnohem rychleji. Jedna implementace může být popsána jako uspořádání datové sekvence v dvourozměrném poli a následné třídění sloupců pole pomocí řazení.

Nejhorší časová složitost Shellsortu je otevřený problém a závisí na použité sekvenci mezer se známými složitostmi od Ó(n²) až Ó(n^4/3) a Θ (n log² n). To v kombinaci se skutečností, že Shellsort je na místě, potřebuje pouze relativně malé množství kódu a nevyžaduje použití zásobník volání, je užitečné v situacích, kdy je paměť špičková, například v vestavěné systémy a jádra operačního systému.

Třídění bublin a varianty

Třídění bublin a varianty jako druh skořápky a koktejl, jsou jednoduché, vysoce neúčinné třídicí algoritmy. Často jsou vidět v úvodních textech kvůli snadné analýze, ale v praxi se používají jen zřídka.

Třídění bublin

Třídění bublin, algoritmus třídění, který neustále prochází seznamem výměna položky, dokud se nezobrazí ve správném pořadí.

Třídění bublin je jednoduchý třídicí algoritmus. Algoritmus začíná na začátku datové sady. Porovnává první dva prvky a pokud je první větší než druhý, vymění je. Pokračuje v tom pro každou dvojici sousedních prvků až do konce datové sady. Poté začíná znovu s prvními dvěma prvky a opakuje se, dokud při posledním průchodu nedojde k žádné výměně.^[33] Průměrná doba 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. Bubble sort lze použít k třídění malého počtu položek (kde jeho asymptotická neefektivita není vysokým trestem). Třídění bublin lze také efektivně použít na seznam libovolné délky, která je téměř tříděna (tj. Prvky nejsou výrazně mimo místo). Například pokud libovolný počet prvků není na místě pouze o jednu pozici (např. 0123546789 a 1032547698), výměna bublinového řazení je získá v pořadí při prvním průchodu, druhý průchod najde všechny prvky v pořadí, takže řazení bude vzít jen 2n čas.

^[34]

Hřeben třídění

Hřeben třídění je relativně jednoduchý třídicí algoritmus založený na třídění bublin a původně navrhl Włodzimierz Dobosiewicz v roce 1980.^[35] To bylo později nově objevené a popularizované Stephen Lacey a Richard Box s Byte Časopis článek publikovaný v dubnu 1991. Základní myšlenkou je eliminovat želvy, nebo malé hodnoty na konci seznamu, protože v třídění podle bublin tyto třídění ohromně zpomalují. (Králíci, velké hodnoty kolem začátku seznamu, nepředstavují problém při třídění bublin) Toho dosáhne tím, že nejprve zamění prvky, které jsou v poli v určité vzdálenosti od sebe, spíše než jen zaměňuje prvky, pokud k sobě sousedí , a poté zmenšovat zvolenou vzdálenost, dokud nebude fungovat jako normální druh bubliny. Pokud tedy lze Shellsort považovat za zobecněnou verzi druhu vkládání, která zaměňuje prvky rozmístěné v určité vzdálenosti od sebe, lze hřebenový druh považovat za stejnou generalizaci použitou pro třídění bublin.

Třídění distribuce

Třídění distribuce odkazuje na jakýkoli třídicí algoritmus, 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 obojí kbelík třídění a flashsort jsou distribuční třídicí algoritmy. Algoritmy třídění distribuce lze použít na jednom procesoru nebo mohou být distribuovaný algoritmus, kde jsou jednotlivé podmnožiny odděleně tříděny na různých procesorech a poté kombinovány. To dovoluje externí třídění dat příliš velkých na to, aby se vešly do paměti jednoho počítače.

Počítání řazení

Počítání řazení je použitelné, když je známo, že každý vstup patří do konkrétní sady, Smožností. Algoritmus běží v O (|S| + n) čas a O (|S|) paměť kde n je délka vstupu. Funguje to tak, že vytvoříte celé číslo o velikosti |S| a pomocí ith bin počítat výskyty ith člen S ve vstupu. Každý vstup se poté počítá zvýšením hodnoty jeho odpovídajícího zásobníku. Poté je počítací pole smyčkou uspořádáno všechny vstupy v pořádku. Tento třídicí algoritmus často nelze použít, protože S musí být přiměřeně malý, aby byl algoritmus efektivní, ale je extrémně rychlý a vykazuje skvělé asymptotické chování jako n zvyšuje. Lze jej také upravit tak, aby poskytoval stabilní chování.

Třídění kbelíku

Třídění kbelíku je rozděl a panuj algoritmus třídění, který zobecňuje počítání řazení rozdělením pole na konečný počet segmentů. Každý segment je poté tříděn jednotlivě, buď pomocí jiného třídicího algoritmu, nebo rekurzivním použitím třídicího algoritmu segmentu.

Třídění segmentu funguje nejlépe, když jsou prvky datové sady rovnoměrně rozloženy ve všech segmentech.

Radix třídění

Radix třídění je algoritmus, který třídí čísla zpracováním jednotlivých číslic. n čísla skládající se z k číslice jsou seřazeny podle O (n · k) čas. Radix sort dokáže zpracovat číslice každého čísla počínaje od nejméně významná číslice (LSD) nebo od nejvýznamnější číslice (MSD). Algoritmus LSD nejprve seřadí seznam podle nejméně významné číslice při zachování jejich relativního pořadí pomocí stabilního řazení. Potom je seřadí podle další číslice atd. Od nejméně významné po nejvýznamnější a skončí seřazeným seznamem. Zatímco třídění radixů LSD vyžaduje použití stabilního třídění, algoritmus třídění radixů MSD není (pokud není požadováno stabilní třídění). Řazení radixů na místě MSD není stabilní. Je to běžné pro počítání řazení algoritmus, který má být interně používán radixovým druhem. A hybridní třídicí přístup, například použití třídění vložení u malých zásobníků významně zlepšuje výkon radixového řazení.

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

Když se velikost pole, které má být tříděno, blíží nebo přesahuje dostupnou primární paměť, takže musí být použit (mnohem pomalejší) disk nebo odkládací prostor, stane se důležitým vzor využití paměti třídicího algoritmu a algoritmus, který mohl být docela 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 opakování částí paměti, které je třeba zkopírovat nebo vyměnit za na disk, může dominovat výkonovým charakteristikám algoritmu. Počet průchodů a lokalizace srovnání může být tedy důležitější než surový počet srovnání, protože srovnání blízkých prvků k sobě probíhají v systémová sběrnice rychlost (nebo při ukládání do mezipaměti, dokonce při procesor rychlost), která je ve srovnání s rychlostí disku prakticky okamžitá.

Například populární rekurzivní quicksort Algoritmus poskytuje docela rozumný výkon s adekvátní 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 RAM, protože to může způsobit řadu pomalých operací kopírování nebo přesunu do a z disku. V tomto scénáři může být vhodnější jiný algoritmus, i když vyžaduje více celkových srovnání.

Jeden způsob, jak vyřešit tento problém, který funguje dobře, když jsou složité záznamy (například v a relační databáze ) jsou tříděny podle relativně malého pole klíče, je vytvořit index do pole a poté seřadit index, nikoli celé pole. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem. This procedure is sometimes called "tag sort".^[36]

Another technique for overcoming the memory-size problem is using externí třídění, for example one of the ways is to combine two algorithms in a way that takes advantage of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit in RAM, the contents of each chunk sorted using an efficient algorithm (such as quicksort ), and the results merged using a k-way merge similar to that used in Sloučit třídění. This is faster than performing either mergesort or quicksort over the entire list.^[37][38]

Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtuální paměť, i.e., to reduce the amount of swapping required.

Related algorithms

Related problems include partial sorting (sorting only the k smallest elements of a list, or alternatively computing the k smallest elements, but unordered) and výběr (computing the kth smallest element). These can be solved inefficiently by a total sort, but more efficient algorithms exist, often derived by generalizing a sorting algorithm. The most notable example is quickselect, which is related to quicksort. Conversely, some sorting algorithms can be derived by repeated application of a selection algorithm; quicksort and quickselect can be seen as the same pivoting move, differing only in whether one recurses on both sides (quicksort, rozděl a panuj ) or one side (quickselect, decrease and conquer ).

A kind of opposite of a sorting algorithm is a shuffling algorithm. These are fundamentally different because they require a source of random numbers. Shuffling can also be implemented by a sorting algorithm, namely by a random sort: assigning a random number to each element of the list and then sorting based on the random numbers. This is generally not done in practice, however, and there is a well-known simple and efficient algorithm for shuffling: the Fisher – Yates zamíchá.

Viz také

• Třídění – Assembly of written information into a standard order
• Schwartzian transform
• Vyhledávací algoritmus – Any algorithm which solves the search problem
• Kvantové třídění – Sorting algorithms for quantum computers

Reference

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Září 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Další čtení

• Knuth, Donald E. (1998), Třídění a vyhledávání, 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, pp. 101–130, ISBN  0-12-394680-8

externí odkazy

• Sorting Algorithm Animations na Wayback Machine (archived 3 March 2015)
• Sequential and parallel sorting algorithms – explanations and analyses of many sorting algorithms
• Dictionary of Algorithms, Data Structures, and Problems – dictionary of algorithms, techniques, common functions, and problems
• Slightly Skeptical View on Sorting Algorithms – Discusses several classic algorithms and promotes alternatives to the quicksort algoritmus
• 15 Sorting Algorithms in 6 Minutes (Youtube) – visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes
• A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements" – which performed by Ford–Johnson algorithm
• Sorting Algorithms Used on Famous Paintings (Youtube) - Visualization of Sorting Algorithms on Many Famous Paintings.