Sortare numărătoare

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 18 ianuarie 2019; verificările necesită 29 de modificări .

Counting sort [1] ( eng. counting sort [2] ; sorting by counting [3] eng. sorting by counting [4] ) este un algoritm de sortare care utilizează un interval de numere dintr-o matrice sortată ( listă ) pentru a număra elementele care se potrivesc . Utilizarea sortării de numărare este utilă numai atunci când numerele sortate au (sau pot fi mapate la) un interval de valori posibile suficient de mic în comparație cu setul sortat, de exemplu, un milion de numere naturale mai mici de 1000.

Să presupunem că tabloul de intrare este format din numere întregi în intervalul de la , unde . În plus, algoritmul va fi generalizat pentru un interval de numere întregi arbitrare. Există mai multe modificări de sortare de numărare, mai jos sunt trei liniare și una pătratică, care utilizează o abordare diferită, dar are același nume. $n$ $0$ $k-1$ $k \in \mathbb N$

Un algoritm simplu

Aceasta este cea mai simplă versiune a algoritmului. Creați o matrice auxiliară C[0..k]constând din zerouri, apoi citiți secvențial elementele matricei de intrare , crescând cu câte unul Apentru fiecare . Acum este suficient să parcurgeți matricea , pentru fiecare din matrice să scrieți succesiv numărul j ori. A[i]C[A[i]]C $j\in \{0,...,k\)$ AC[j]

SimpleCountingSort: pentru i = 0 la k C[i] = 0; pentru i = 0 până la n - 1 C[A[i]] = C[A[i]] + 1; b = 0; pentru j = 0 la k pentru i = 0 la C[j] - 1 A[b] = j; b = b + 1;

Implementare în C :

//matrice - indicator la începutul matricei //n - dimensiunea matricei //k - numărul maxim în matrice void countingSort ( int * matrice , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * sizeof ( * array )); memset ( c , 0 , sizeof ( * array ) * ( k + 1 )); pentru ( int i = 0 ; i < n ; ++ i ) { ++ c [ matrice [ i ]]; } int b = 0 ; pentru ( int i = 0 ; i < k + 1 ; ++ i ){ pentru ( int j = 0 ; j < c [ i ]; ++ j ) { matrice [ b ++ ] = i ; } } liber ( c ); }

Implementare în C++ :

#include <vector> #include <type_traits> #include <algoritm> template < typename std :: enable_if_t < std :: is_integral_v < T > , T >> void countingSort ( std :: vector < T >& array ) { T max = std :: element_max ( array .begin (), array .end ( ) ); auto count = std :: vector < T > ( max + 1 , T ( 0 )); pentru ( T elem : matrice ) ++ c [ elem ]; T b = 0 ; pentru ( dimensiunea_t i = 0 ; i < max + 1 ; ++ i ) { pentru ( T j = 0 ; j < count [ i ]; ++ j ) { matrice [ b ++ ] = i ; } } }

Algoritmul listei

Această variantă ( sortare în case , sortare număr ) este utilizată atunci când intrarea este o matrice de structuri de date care ar trebui sortate după chei ( key). Trebuie să creați o matrice auxiliară C[0..k - 1], fiecare C[i]va conține ulterior o listă de elemente din matricea de intrare. Apoi citiți secvențial elementele matricei de intrare , adăugându - Ale pe fiecare în listă . În concluzie, parcurgeți matricea , pentru fiecare matrice , scrieți secvențial elementele listei . Algoritmul este stabil . A[i]C[A[i].key]C $j \in \{0, ..., k - 1\}$ AC[j]

ListCountingSort pentru i = 0 la k - 1 C[i] = NULL; pentru i = 0 până la n - 1 C[A[i].key].add(A[i]); b = 0; pentru j = 0 la k - 1 p = C[j]; în timp ce p != NULL A[b] = p.data; p = p.next(); b = b + 1;

Algoritm robust

În această variantă, pe lângă matricea de intrare, Asunt necesare două matrice auxiliare - C[0..k - 1]pentru contor și B[0..n - 1]pentru matricea sortată. Mai întâi, umpleți tabloul cu Czerouri și pentru fiecare A[i]creștere C[A[i]]cu 1. Apoi, numărul de elemente mai mic sau egal cu este numărat . Pentru a face acest lucru, fiecare , începând de la , este mărit cu . Astfel, ultima celulă va conține numărul de elemente de la până la existente în tabloul de intrare. La ultimul pas al algoritmului, matricea de intrare este citită de la sfârșit, valoarea este redusă cu 1 și . Algoritmul este stabil. $k-1$ C[j]C[1]C[j - 1] $0$ $k-1$ C[A[i]]B[C[A[i]]]A[i]

StableCountingSort pentru i = 0 la k - 1 C[i] = 0; pentru i = 0 până la n - 1 C[A[i]] = C[A[i]] + 1; pentru j = 1 până la k - 1 C[j] = C[j] + C[j-1]; pentru i = n - 1 la 0 C[A[i]] = C[A[i]] - 1; B[C[A[i]]] = A[i];

Generalizare la un interval de numere întregi arbitrare

Apar mai multe întrebări. Ce se întâmplă dacă intervalul de valori (min și max) nu este cunoscut în prealabil? Ce se întâmplă dacă valoarea minimă este mai mare decât zero sau există numere negative în datele sortate? Prima întrebare poate fi rezolvată printr-o căutare liniară pentru min și max, care nu va afecta asimptoticele algoritmului. A doua întrebare este ceva mai dificilă. Dacă min este mai mare decât zero, scădeți min din matrice când lucrați cu matrice și adăugați min când scrieți înapoi C. A[i]Dacă există numere negative, trebuie Csă A[i]adăugați la când lucrați cu o matrice |min|și să scădeți când scrieți înapoi.

Analiză

În primii doi algoritmi, primele două bucle funcționează pentru și , respectiv; ciclu dublu pentru . În al treilea algoritm, ciclurile iau , , și , respectiv. În total, toți cei trei algoritmi au o complexitate de timp liniară . Memoria folosită în primii doi algoritmi este , iar în al treilea . $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n)$ $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n+k)$

Algoritmul de sortare de numărare pătratică

Sortarea de numărare se mai numește și algoritm ușor diferit. Folosește o matrice de intrare Ași o matrice auxiliară Bpentru setul sortat. În algoritm, pentru fiecare element al matricei de intrare, A[i]numărați numărul de elemente mai mic decât acesta și numărul de elemente egal cu acesta, dar în picioare mai devreme ( ). atribuie . Algoritmul este stabil. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ B[c]A[i]

SquareCountingSort pentru i = 0 până la n - 1 c = 0; pentru j = 0 la i - 1 dacă A[j] <= A[i] c = c + 1; pentru j = i + 1 la n - 1 dacă A[j] < A[i] c = c + 1; B[c] = A[i];

Analiză

Evident, timpul estimat al algoritmului este , memorie . $\Theta (n^{2})$ $\Theta(n)$

Exemple de implementare

Componenta Pascal

Algoritm simplu.

PROCEDURA CountingSort ( VAR a : MATRICE DE INTEGER ; min , max : INTEGER ) ; VAR i , j , c : INTEGER ; b : POINTER LA MATRICE DE INTEGER ; BEGIN ASSERT ( min <= max ) ; NOU ( b , max - min + 1 ) ; FOR i := 0 TO LEN ( a ) - 1 DO INC ( b [ a [ i ] - min ]) END ; i := 0 ; FOR j := min TO max DO c := b [ j - min ] ; WHILE c > 0 DO a [ i ] := j ; INC ( i ) ; DEC ( c ) END END END CountingSort ;

Implementare în PascalABC.Net

const n = 20 _ ÎNCEPE var a := ArrRandomInteger ( n , 0 , 100 ) ; a . Println ; var max := a . Max ; var c := | 0 | * ( max + 1 ) ; pentru var i := 0 la a . Lungime - 1 do c [ a [ i ]] += 1 ; var j := 0 ; pentru var i := 0 la max do pentru var k := 1 la c [ i ] do ÎNCEPE a [ j ] := i ; j += 1 ; sfârşitul ; a . Println ; sfârşitul .

Implementare în Python

a = listă ( hartă ( int , input () . split ())) # citește lista cnt = [ 0 ] * ( max ( a ) + 1 ) # generează o listă de zerouri cu lungimea elementului maxim al listei a pentru articol dintr- o : cnt [ item ] += 1 # când întâlnim un număr în listă, mărim valoarea acestuia cu 1 # adăugați numărul de ori num la rezultat rezultat = [ num for num , count in enumerate ( cnt ) for i in range ( count )] print ( rezultat ) # imprimă lista sortată

Vezi și

Note

↑ Kormen. Sortare de numărare // Algoritmi: un curs introductiv. - Williams, 2014. - S. 71. - 208 p. — 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 (ed. a doua), MIT Press și McGraw-Hill , p. 168–170, ISBN 0-262-03293-7 .
↑ Bici. Sortarea după numărare // Arta programarii. - T. 3. - S. 77.
↑ Knuth, D.E. (1998), Secțiunea 5.2, Sorting by counting, The Art of Computer Programming , Volumul 3: Sorting and Searching (ed. a 2-a), Addison-Wesley, p. 75-80, ISBN 0-201-89685-0 .

Literatură

Levitin A. V. Capitolul 7. Compromisul spațiu-temporal: Sortarea numărării // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 331-339. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capitolul 8 Sortarea în timp liniar // Algoritmi: Construcție și analiză = Introducere în algoritmi. — ediția a II-a. - M . : „Williams” , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Link -uri

Visualizer1 este un applet Java.
Visualizer2 este un applet Java.

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet