Počítat seřadit

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é 18. ledna 2019; kontroly vyžadují 29 úprav .

Počítání řazení [1] ( eng. counting sort [2] ; sorting by counting [3] eng. sorting by counting [4] ) je třídicí algoritmus , který používá rozsah čísel seřazeného pole ( seznam ) k počítání odpovídajících prvků. . Použití řazení počítání je užitečné pouze v případě, že seřazená čísla mají (nebo je lze namapovat) rozsah možných hodnot, který je dostatečně malý ve srovnání se seřazenou sadou, například milion přirozených čísel menší než 1000.

Předpokládejme, že vstupní pole se skládá z celých čísel v rozsahu od do , kde . Dále bude algoritmus zobecněn pro libovolný rozsah celých čísel. Existuje několik modifikací řazení počítání, níže jsou tři lineární a jedna kvadratická, která používá jiný přístup, ale má stejný název. $n$ $0$ $k-1$ $k \in \mathbb N$

Jednoduchý algoritmus

Toto je nejjednodušší verze algoritmu. Vytvořte pomocné pole C[0..k]sestávající z nul a poté postupně čtěte prvky vstupního pole , přičemž Apro každý A[i]zvyšujte o jednu C[A[i]]. Nyní stačí pole projít C, pro každý v poli postupně napsat číslo j krát. $j\in \{0,...,k\}$ AC[j]

SimpleCountingSort: pro i = 0 až k C[i] = 0; pro i = 0 až n-1 C[A[i]] = C[A[i]] + 1; b = 0; pro j = 0 až k pro i = 0 až C[j]-1 A[b] = j; b = b + 1;

Implementace v C :

//pole - ukazatel na začátek pole //n - velikost pole //k - maximální počet v poli void countingSort ( int * pole , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * sizeof ( * pole )); memset ( c , 0 , sizeof ( * pole ) * ( k + 1 )); for ( int i = 0 ; i < n ; ++ i ) { ++ c [ pole [ i ]]; } int b = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ){ for ( int j = 0 ; j < c [ i ]; ++ j ) { pole [ b ++ ] = i ; } } volný ( c ); }

Implementace v C++ :

#include <vektor> #include <type_traits> #include <algoritmus> template < typename std :: enable_if_t < std :: is_integral_v < T > , T >> void countingSort ( std :: vector < T >& pole ) { T max = std :: max_element ( pole .začátek (), pole .konec ( ) ); auto count = std :: vektor < T > ( max + 1 , T ( 0 )); pro ( T elem : pole ) ++ c [ elem ]; Tb = 0 ; _ for ( size_t i = 0 ; i < max + 1 ; ++ i ) { for ( T j = 0 ; j < počet [ i ]; ++ j ) { pole [ b ++ ] = i ; } } }

Algoritmus seznamu

Tato varianta ( rozškatulkování , řazení podle počtu ) se používá, když je vstupem pole datových struktur, které by měly být seřazeny podle klíčů ( key). Musíte vytvořit pomocné pole C[0..k - 1], každé C[i]bude později obsahovat seznam prvků ze vstupního pole. Poté postupně přečtěte prvky vstupního pole a přidejte Akaždý z nich do seznamu . Na závěr projděte pole , pro každé pole postupně zapište prvky seznamu . Algoritmus je stabilní . A[i]C[A[i].key]C $j \in \{0, ..., k - 1\}$ AC[j]

SeznamPočítáníSeřadit pro i = 0 až k-1 C[i] = NULL; pro i = 0 až n-1 C[A[i].key].add(A[i]); b = 0; pro j = 0 až k-1 p = C[j]; zatímco p != NULL A[b] = p.data; p = p.další(); b = b + 1;

Robustní algoritmus

V této variantě jsou kromě vstupního pole Azapotřebí dvě pomocná pole - C[0..k - 1]pro čítač a B[0..n - 1]pro pole tříděné. Nejprve vyplňte pole Cnulami a pro každé A[i]zvýšení C[A[i]]o 1. Dále se počítá počet prvků menší nebo roven . Za tímto účelem se každý , počínaje , zvýší o . Poslední buňka tedy bude obsahovat počet prvků od do existujících ve vstupním poli. V posledním kroku algoritmu se vstupní pole načte od konce, hodnota se sníží o 1 a . Algoritmus je stabilní. $k-1$ C[j]C[1]C[j - 1] $0$ $k-1$ C[A[i]]B[C[A[i]]]A[i]

StableCountingSort pro i = 0 až k-1 C[i] = 0; pro i = 0 až n-1 C[A[i]] = C[A[i]] + 1; pro j = 1 až k-1 C[j] = C[j] + C[j-1]; pro i = n-1 až 0 C[A[i]] = C[A[i]] - 1; B[C[A[i]]] = A[i];

Zobecnění na libovolný rozsah celých čísel

Nabízí se několik otázek. Co když rozsah hodnot (min a max) není předem znám? Co když je minimální hodnota větší než nula nebo jsou v seřazených datech záporná čísla? První otázku lze vyřešit lineárním hledáním min a max, které neovlivní asymptotiku algoritmu. Druhá otázka je poněkud složitější. Pokud je min větší než nula, odečtěte min od pole při práci s polem a přidejte min při zpětném zápisu C. A[i]Pokud existují záporná čísla, musíte Cpři práci s polem A[i]přidat k |min|a při zpětném zápisu odečíst.

Analýza

V prvních dvou algoritmech fungují první dvě smyčky pro a ; dvojitý cyklus pro . Ve třetím algoritmu cykly berou , , a , v tomto pořadí. Celkově mají všechny tři algoritmy lineární časovou složitost . Paměť použitá v prvních dvou algoritmech je , a ve třetím . $\Theta(k)$ $\Opalování)$ $\Theta(n+k)$ $\Theta(k)$ $\Opalování)$ $\Theta(k)$ $\Opalování)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n+k)$

Algoritmus řazení kvadratického počítání

Třídění počítání se také nazývá mírně odlišný algoritmus. Pro seřazenou množinu používá vstupní pole Aa pomocné pole . BV algoritmu pro každý prvek vstupního pole A[i]spočítejte počet prvků menší než je on a počet prvků, které jsou mu rovné, ale stojí dříve ( ). přiřadit . Algoritmus je stabilní. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ B[c]A[i]

SquareCountingSort pro i = 0 až n-1 c = 0; pro j = 0 až i-1 pokud A[j] <= A[i] c = c + 1; pro j = i + 1 až n - 1 pokud A[j] < A[i] c = c + 1; B[c] = A[i];

Analýza

Je zřejmé, že časový odhad algoritmu je , paměť . $\Theta (n^{2})$ $\Opalování)$

Příklady implementace

Komponenta Pascal

Jednoduchý algoritmus.

PROCEDURE CountingSort ( VAR a : ARRAY OF INTEGER ; min , max : INTEGER ) ; VAR i , j , c : INTEGER ; b : UKAZATEL NA POLE CELÉHO ČÍSLA ; BEGIN ASSERT ( min <= max ) ; NOVÝ ( b , max - min + 1 ) ; FOR i := 0 DO DÉLKY ( a ) - 1 DO INC ( b [ a [ i ] - min ]) KONEC ; i := 0 ; FOR j := min DO max DO c := b [ j - min ] ; KDYŽ c > 0 UDĚLEJTE a [ i ] := j ; INC ( i ) ; DEC ( c ) KONEC KONEC KONEC CountingSort ;

Implementace v PascalABC.Net

konst n = 20 _ začít var a := ArrRandomInteger ( n , 0 , 100 ) ; a _ Println ; var max := a . Max ; var c := | 0 | * ( max + 1 ) ; pro var i := 0 až a . Délka - 1 do c [ a [ i ]] += 1 ; var j := 0 ; pro var i := 0 až max do pro var k := 1 až c [ i ] do začít a [ j ] := i ; j += 1 ; konec ; a _ Println ; konec .

Implementace v Pythonu

a = seznam ( mapa ( int , vstup () . rozdělení ())) # přečíst seznam cnt = [ 0 ] * ( max ( a ) + 1 ) # vygenerovat seznam nul s délkou maximálního prvku seznamu a pro položku v : _ cnt [ položka ] += 1 # když narazíme na číslo v seznamu, zvyšte jeho hodnotu o 1 # k výsledku přidejte počet krát num výsledek = [ num pro num , počet ve výčtu ( cnt ) pro i v rozsahu ( počet )] print ( result ) # tisk seřazeného seznamu

Viz také

Poznámky

↑ Kormen. Počítání řazení // Algoritmy: Úvodní kurz. - Williams, 2014. - S. 71. - 208 s. — ISBN 978-5-8459-1868-0 .
↑ Cormen, Thomas H. ; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2. ed.), MIT Press and McGraw-Hill , str. 168–170, ISBN 0-262-03293-7 .
↑ Bič. Třídění počítáním // Umění programování. - T. 3. - S. 77.
↑ Knuth, D. E. (1998), oddíl 5.2, Sorting by counting, The Art of Computer Programming , Volume 3: Sorting and Searching (2nd ed.), Addison-Wesley, str. 75-80, ISBN 0-201-89685-0 .

Literatura

Levitin A. V. Kapitola 7. Space-Time Compromise: Counting Sorting // Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 331-339. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitola 8 Třídění v lineárním čase // Algoritmy: Konstrukce a analýza = Úvod do algoritmů. — 2. vydání. - M .: "Williams" , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Odkazy

Visualizer1 je Java applet.
Visualizer2 je Java applet.

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ý