Tæl sortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 18. januar 2019; checks kræver 29 redigeringer .

Tællesort [1] ( eng. counting sort [2] ; sortering ved at tælle [3] eng. sortering ved at tælle [4] ) er en sorteringsalgoritme , der bruger en række af tal fra en sorteret matrix ( liste ) til at tælle matchende elementer . Brugen af tællesort er kun nyttig, når de sorterede tal har (eller kan kortlægges til) en række mulige værdier, der er små nok sammenlignet med det sorterede sæt, for eksempel en million naturlige tal mindre end 1000.

Lad os antage, at input-arrayet består af heltal i intervallet fra til , hvor . Yderligere vil algoritmen blive generaliseret for et vilkårligt heltalsområde. Der er flere modifikationer af tællesortering, nedenfor er tre lineære og en kvadratisk, som bruger en anden tilgang, men har samme navn. $n$ $0$ $k-1$ $k \in \mathbb N$

En simpel algoritme

Dette er den enkleste version af algoritmen. Opret et hjælpearray C[0..k]bestående af nuller, og læs derefter elementerne i input-arrayet sekventielt , hvilket øges med én Afor hver . Nu er det nok at gå gennem arrayet , for hver i arrayet skriver sekventielt tallet j gange. A[i]C[A[i]]C ${\displaystyle j\in \{0,...,k\))$ AC[j]

SimpleCountingSort: for i = 0 til k C[i] = 0; for i = 0 til n - 1 C[A[i]] = C[A[i]] + 1; b = 0; for j = 0 til k for i = 0 til C[j] - 1 A[b] = j; b = b + 1;

Implementering i C :

//array - pointer til begyndelsen af arrayet //n - array size //k - maksimum antal i arrayet void countingSort ( int * array , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * størrelse på ( * array )); memset ( c , 0 , størrelse af ( * array ) * ( k + 1 )); for ( int i = 0 ; i < n ; ++ i ) { ++ c [ array [ i ]]; } int b = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ){ for ( int j = 0 ; j < c [ i ]; ++ j ) { matrix [ b ++ ] = i ; } } fri ( c ); }

Implementering i C++ :

#inkluder <vektor> #include <type_træk> #include <algoritme> skabelon < typenavn 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 ( ) ); autotælling = std :: vektor < T > ( max + 1 , T ( 0 ) ); for ( T elem : array ) ++ c [ elem ]; Tb = 0 ; _ for ( størrelse_t i = 0 ; i < maks + 1 ; ++ i ) { for ( T j = 0 ; j < count [ i ]; ++ j ) { matrix [ b ++ ] = i ; } } }

Listealgoritme

Denne variant ( duehulssortering , tællesortering ) bruges, når inputtet er en række datastrukturer, der skal sorteres efter nøgler ( key). Du skal oprette et hjælpearray C[0..k - 1], hver C[i]vil senere indeholde en liste over elementer fra input-arrayet. Læs derefter sekventielt elementerne i input-arrayet , og føj Ahver enkelt til listen . Afslutningsvis skal du gennemgå arrayet , for hvert array , skriv sekventielt elementerne i listen . Algoritmen er stabil . A[i]C[A[i].key]C $j \i \{0, ..., k - 1\}$ AC[j]

ListCountingSort for i = 0 til k - 1 C[i] = NULL; for i = 0 til n - 1 C[A[i].nøgle].add(A[i]); b = 0; for j = 0 til k - 1 p = C[j]; mens p != NULL A[b] = p.data; p = p.next(); b = b + 1;

Robust algoritme

I denne variant kræves der udover input-arrayet Ato hjælpearrays - C[0..k - 1]til tælleren og B[0..n - 1]til det sorterede array. Fyld først arrayet med Cnuller, og for hver A[i]stigning C[A[i]]med 1. Dernæst tælles antallet af elementer mindre end eller lig med . For at gøre dette øges hver , startende fra , med . Den sidste celle vil således indeholde antallet af elementer fra til eksisterende i input-arrayet. Ved det sidste trin af algoritmen læses input-arrayet fra slutningen, værdien reduceres med 1 og . Algoritmen er stabil. $k-1$ C[j]C[1]C[j - 1] $0$ $k-1$ C[A[i]]B[C[A[i]]]A[i]

StableCountingSort for i = 0 til k - 1 C[i] = 0; for i = 0 til n - 1 C[A[i]] = C[A[i]] + 1; for j = 1 til k - 1 C[j] = C[j] + C[j-1]; for i = n - 1 til 0 C[A[i]] = C[A[i]] - 1; B[C[A[i]]] = A[i];

Generalisering til et vilkårligt heltalsområde

Der opstår flere spørgsmål. Hvad hvis rækkevidden af værdier (min og max) ikke er kendt på forhånd? Hvad hvis minimumsværdien er større end nul, eller der er negative tal i de sorterede data? Det første spørgsmål kan løses ved en lineær søgning efter min og max, hvilket ikke vil påvirke algoritmens asymptotik. Det andet spørgsmål er noget sværere. Hvis min er større end nul, skal du trække min fra arrayet, når du arbejder med arrayet, og tilføje min når du skriver tilbage C. A[i]Hvis der er negative tal, skal Cdu A[i]lægge til, når du arbejder med en matrix |min|, og trække fra, når du skriver tilbage.

Analyse

I de to første algoritmer arbejder de to første sløjfer for henholdsvis og ; dobbelt cyklus for . I den tredje algoritme tager cyklusserne henholdsvis , , og . I alt har alle tre algoritmer en lineær tidskompleksitet . Hukommelsen brugt i de to første algoritmer er , og 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)$

Quadratic Counting Sort Algorithm

Optællingssortering kaldes også en lidt anderledes algoritme. Den bruger et input-array Aog et aux-array Btil det sorterede sæt. I algoritmen tæller du for hvert element i input-arrayet A[i]antallet af elementer, der er mindre end det, og antallet af elementer, der er lig med det, men som står tidligere ( ). tildele . Algoritmen er stabil. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ B[c]A[i]

SquareCountingSort for i = 0 til n - 1 c = 0; for j = 0 til i - 1 hvis A[j] <= A[i] c = c + 1; for j = i + 1 til n - 1 hvis A[j] < A[i] c = c + 1; B[c] = A[i];

Analyse

Det er klart, tidsestimatet for algoritmen er hukommelse . $\Theta (n^{2})$ $\Theta(n)$

Implementeringseksempler

Komponent Pascal

Simpel algoritme.

PROCEDURE CountingSort ( VAR a : MÆLLING AF HELTAL ; min , maks .: HELTAL ) ; VAR i , j , c : HELTAL ; b : PEGLER TIL MATERIALET AF HELTAL ; BEGIN ASSERT ( min <= max ) ; NY ( b , max - min + 1 ) ; FOR i := 0 TIL LEN ( a ) - 1 DO INC ( b [ a [ i ] -min ] ) END ; i := 0 ; FOR j := min TO max DO c := b [ j - min ] ; MENS c > 0 GØR a [ i ] := j ; INC ( i ) ; DEC ( c ) END END END CountingSort ;

Implementering i PascalABC.Net

konst n = 20 _ begynde var a := ArrRandomInteger ( n , 0 , 100 ) ; a . Println ; var max := a . Max ; var c := | 0 | * ( max + 1 ) ; for var i := 0 til a . Længde - 1 do c [ a [ i ]] += 1 ; var j := 0 ; for var i := 0 til max do for var k := 1 til c [ i ] do begynde a [ j ] := i ; j += 1 ; ende ; a . Println ; ende .

Implementering i Python

a = liste ( map ( int , input () . split ())) # læs listen cnt = [ 0 ] * ( max ( a ) + 1 ) # generer en liste med nuller med længden af det maksimale element i listen a for vare i en : cnt [ item ] += 1 # når vi støder på et tal på listen, øger dets værdi med 1 # tilføj tæller gange num til resultatet resultat = [ tal for tal , tæl i opregn ( cnt ) for i i område ( antal )] print ( resultat ) # udskriv den sorterede liste

Se også

Noter

↑ Kormen. Tællesort // Algoritmer: Et introduktionskursus. - 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. udgave), MIT Press og McGraw-Hill , s. 168-170, ISBN 0-262-03293-7 .
↑ Pisk. Sortering ved at tælle // The Art of Programming. - T. 3. - S. 77.
↑ Knuth, D.E. (1998), Afsnit 5.2, Sortering efter tælling, The Art of Computer Programming , bind 3: Sortering og søgning (2. udgave), Addison-Wesley, s. 75-80, ISBN 0-201-89685-0 .

Litteratur

Levitin A. V. Kapitel 7. Rum-temporalt kompromis: Tællesortering // Algoritmer. Introduktion til udvikling og analyse - 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. Kapitel 8 Sortering i lineær tid // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. — 2. udgave. - M . : "Williams" , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Links

Visualizer1 er en Java-applet.
Visualizer2 er en Java-applet.

Sorteringsalgoritmer
Teori	Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling	boble Omrøring Dværge Hurtig Kam Sortering lige-ulige Bitvis
Valg	Valg Pyramideformet Glat
indsætter	indsætter shella træ
fusion	fusion
Ingen sammenligninger	Tæller blok
hybrid	introsort Timsort
Andet	Topologisk netværk biton
upraktisk	Bogosort Stooge sort pandekage langsom