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.
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]]CAC[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 ; } } }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]CAC[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;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. C[j]C[1]C[j - 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];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.
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 .
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. 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];Uppenbarligen är tidsuppskattningen av algoritmen , minne .
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 ;Sorteringsalgoritmer | |
---|---|
Teori | Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern |
Utbyta | |
Val | |
Insatser | |
fusion | |
Inga jämförelser | |
hybrid | |
Övrig | |
opraktisk |