Räkna sortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 januari 2019; kontroller kräver 29 redigeringar .

Counting sort [1] ( eng. counting sort [2] ; sortering genom att räkna [3] eng. sortering genom att räkna [4] ) är en sorteringsalgoritm som använder ett antal nummer i en sorterad array ( lista ) för att räkna matchande element . Användningen av räknesortering är endast användbar när de sorterade talen har (eller kan mappas till) ett intervall av möjliga värden som är tillräckligt litet jämfört med den sorterade uppsättningen, till exempel en miljon naturliga tal mindre än 1000.

Låt oss anta att inmatningsmatrisen består av heltal i intervallet från till , där . Vidare kommer algoritmen att generaliseras för ett godtyckligt heltalsområde. Det finns flera modifieringar av räkningssort, nedan är tre linjära och en kvadratisk, som använder ett annat tillvägagångssätt, men har samma namn. $n$ $0$ $k-1$ $k \in \mathbb N$

En enkel algoritm

Detta är den enklaste versionen av algoritmen. Skapa en hjälpmatris som C[0..k]består av nollor och läs sedan elementen i inmatningsmatrisen sekventiellt och ökar med en Aför varje . Nu räcker det att gå igenom arrayen , för var och en i arrayen skriver sekventiellt antalet j gånger. A[i]C[A[i]]C ${\displaystyle j\in \{0,...,k\))$ AC[j]

SimpleCountingSort: för i = 0 till k C[i] = 0; för i = 0 till n - 1 C[A[i]] = C[A[i]] + 1; b = 0; för j = 0 till k för i = 0 till C[j] - 1 A[b] = j; b = b + 1;

Implementering i C :

//array-pekare till början av arrayen //n-arraystorlek //k - maximalt antal i arrayen void countingSort ( int * array , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * storlek på ( * array )); memset ( c , 0 , storlek på ( * array ) * ( k + 1 )); for ( int i = 0 ; i < n ; ++ i ) { ++ c [ matris [ i ]]; } int b = 0 ; för ( int i = 0 ; i < k + 1 ; ++ i ){ för ( int j = 0 ; j < c [ i ]; ++ j ) { array [ b ++ ] = i ; } } fri ( c ); }

Implementering i C++ :

#inkludera <vektor> #include <type_traits> #inkludera <algoritm> mall < typnamn std :: enable_if_t < std :: is_integral_v < T > , T >> void countingSort ( std :: vektor < T >& array ) { T max = std :: max_element ( array .begin (), array .end ( ) ); auto count = std :: vektor < T > ( max + 1 , T ( 0 )); för ( T elem : array ) ++ c [ elem ]; Tb = O ; _ för ( storlek_t i = 0 ; i < max + 1 ; ++ i ) { för ( Tj = 0 ; j < count [ i ] ; ++ j ) { array [ b ++ ] = i ; } } }

Listalgoritm

Denna variant ( duvhålssortering , count sort ) används när indata är en rad datastrukturer som ska sorteras efter nycklar ( key). Du måste skapa en extra array C[0..k - 1], var och en C[i]kommer senare att innehålla en lista med element från inmatningsarrayen. Läs sedan elementen i inmatningsmatrisen sekventiellt och lägg till Avar och en till listan . Sammanfattningsvis, gå igenom arrayen , för varje array , skriv sekventiellt elementen i listan . Algoritmen är stabil . A[i]C[A[i].key]C $j \i \{0, ..., k - 1\}$ AC[j]

ListCountingSort för i = 0 till k - 1 C[i] = NULL; för i = 0 till n - 1 C[A[i].nyckel].add(A[i]); b = 0; för j = 0 till k - 1 p = C[j]; medan p != NULL A[b] = p.data; p = p.next(); b = b + 1;

Robust algoritm

I denna variant krävs, förutom inmatningsmatrisen, Atvå hjälpmatriser - C[0..k - 1]för räknaren och B[0..n - 1]för den sorterade matrisen. Fyll först matrisen med Cnollor och för varje A[i]ökning C[A[i]]med 1. Därefter räknas antalet element mindre än eller lika med . För att göra detta ökas varje , från och med , med . Således kommer den sista cellen att innehålla antalet element från till existerande i inmatningsmatrisen. I det sista steget i algoritmen läses inmatningsmatrisen från slutet, värdet reduceras med 1 och . Algoritmen är stabil. $k-1$ C[j]C[1]C[j - 1] $0$ $k-1$ C[A[i]]B[C[A[i]]]A[i]

StableCountingSort för i = 0 till k - 1 C[i] = 0; för i = 0 till n - 1 C[A[i]] = C[A[i]] + 1; för j = 1 till k - 1 C[j] = C[j] + C[j-1]; för i = n - 1 till 0 C[A[i]] = C[A[i]]-1; B[C[A[i]]] = A[i];

Generalisering till ett godtyckligt heltalsområde

Flera frågor uppstår. Vad händer om värdeintervallet (min och max) inte är känt i förväg? Vad händer om minimivärdet är större än noll eller det finns negativa tal i den sorterade datan? Den första frågan kan lösas genom en linjär sökning efter min och max, vilket inte kommer att påverka algoritmens asymptotik. Den andra frågan är något svårare. Om min är större än noll, subtrahera min från arrayen när du arbetar med arrayen och lägg till min när du skriver tillbaka C. A[i]Om det finns negativa tal måste du Clägga A[i]till när du arbetar med en array |min|och subtrahera när du skriver tillbaka.

Analys

I de två första algoritmerna fungerar de två första slingorna för respektive ; dubbel cykel för . I den tredje algoritmen tar cyklerna , , respektive . Totalt har alla tre algoritmerna en linjär tidskomplexitet . Minnet som används i de två första algoritmerna är , och i den tredje . $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n)$ $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n+k)$

Kvadratisk räkning Sorteringsalgoritm

Räknesortering kallas också för en lite annorlunda algoritm. Den använder en inmatningsmatris Aoch en hjälpmatris Bför den sorterade uppsättningen. I algoritmen, för varje element i inmatningsmatrisen, A[i]räkna antalet element som är mindre än det och antalet element lika med det, men som står tidigare ( ). tilldela . Algoritmen är stabil. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ B[c]A[i]

SquareCountingSort för i = 0 till n - 1 c = 0; för j = 0 till i - 1 om A[j] <= A[i] c = c + 1; för j = i + 1 till n - 1 om A[j] < A[i] c = c + 1; B[c] = A[i];

Analys

Uppenbarligen är tidsuppskattningen av algoritmen , minne . $\Theta (n^{2})$ $\Theta(n)$

Implementeringsexempel

Komponent Pascal

Enkel algoritm.

PROCEDUR CountingSort ( VAR a : ARRAY OF HELTAL ; min , max : INTEGER ) ; VAR i , j , c : HELTAL ; b : PEKARE TILL ARRAY AV HELTAL ; BÖRJA ANSERT ( min <= max ) ; NYTT ( b , max - min + 1 ) ; FOR i := 0 TO LEN ( a ) - 1 DO INC ( b [ a [ i ] - min ]) END ; i := 0 ; FÖR j := min TO max DO c := b [ j - min ] ; MEDAN c > 0 GÖR a [ i ] := j ; INC ( i ) ; DEC ( c ) END END END CountingSort ;

Implementering i PascalABC.Net

konst n = 20 _ Börja var a := ArrRandomInteger ( n , 0 , 100 ) ; a . Println ; var max := a . Max ; var c := | 0 | * ( max + 1 ) ; för var i := 0 till a . Längd - 1 do c [ a [ i ]] += 1 ; var j := 0 ; för var i := 0 till max do för var k := 1 till c [ i ] do Börja a [ j ] := i ; j += 1 ; slut ; a . Println ; slut .

Implementering i Python

a = lista ( map ( int , input () . split ())) # läs listan cnt = [ 0 ] * ( max ( a ) + 1 ) # generera en lista med nollor med längden på det maximala elementet i listan a för artikel i en : cnt [ item ] += 1 # när vi stöter på ett nummer i listan, öka dess värde med 1 # lägg till antal gånger num till resultatet resultat = [ num för num , count in enumerate ( cnt ) för i i intervallet ( count )] print ( resultat ) # skriv ut den sorterade listan

Se även

Anteckningar

↑ Kormen. Räknesort // Algoritmer: En introduktionskurs. - Williams, 2014. - S. 71. - 208 sid. — 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 (2nd ed.), MIT Press och McGraw-Hill , sid. 168–170, ISBN 0-262-03293-7 .
↑ Piska. Sortera efter räkning // Konsten att programmera. - T. 3. - S. 77.
↑ Knuth, D.E. (1998), Avsnitt 5.2, Sortering efter räkning, The Art of Computer Programming , Volym 3: Sortering och sökning (2nd ed.), Addison-Wesley, sid. 75-80, ISBN 0-201-89685-0 .

Litteratur

Levitin A. V. Kapitel 7. Space-Temporal Compromising: Räknesortering // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 331-339. — 576 sid. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 8 Sortering i linjär tid // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. — 2:a upplagan. - M . : "Williams" , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Länkar

Visualizer1 är en Java-applet.
Visualizer2 är en Java-applet.

Sorteringsalgoritmer
Teori	Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta	bubbla Omrörning Dvärgar Snabb Hårkam Sortering jämnt-udda Bitvis
Val	Val Pyramidformad Slät
Insatser	Insatser shella träd
fusion	fusion
Inga jämförelser	Räkning blockera
hybrid	introsort Timsort
Övrig	Topologiska nätverk biton
opraktisk	Bogosort Stooge sort pannkaka långsam