Tæller sorter - Counting sort

Tæller sorter
Klasse Sorteringsalgoritme
Datastruktur Array
Ydeevne i værste fald , hvor k er intervallet for de ikke-negative nøgleværdier.
Værste kompleksitet i rummet

Inden for datalogi er tælling af sortering en algoritme til sortering af en samling objekter efter nøgler, der er små positive heltal ; det vil sige, det er en heltalssorteringsalgoritme . Det fungerer ved at tælle antallet af objekter, der besidder forskellige nøgleværdier, og anvende præfiks sum på disse tællinger for at bestemme positionerne for hver nøgleværdi i output sekvensen. Dens driftstid er lineær i antallet af emner og forskellen mellem den maksimale nøgleværdi og den mindste nøgleværdi, så den er kun egnet til direkte brug i situationer, hvor variationen i nøgler ikke er væsentligt større end antallet af emner. Det bruges ofte som en underrutine i radix -sortering, en anden sorteringsalgoritme, som kan håndtere større nøgler mere effektivt.

At tælle sorter er ikke en sammenligningssort ; den bruger nøgleværdier som indekser i en matrix, og Ω ( n log n ) undergrænsen for sammenligningssortering finder ikke anvendelse. Skovlesortering kan bruges i stedet for at tælle sortering og indebærer en lignende tidsanalyse. I forhold til at tælle sortering kræver bucket-sortering imidlertid sammenkædede lister , dynamiske arrays eller en stor mængde forudallokeret hukommelse for at holde sæt af elementer inden for hver bucket, hvorimod tællesortering gemmer et enkelt nummer (antallet af varer) pr. Spand .

Input og output antagelser

I det mest generelle tilfælde består input til tællesortering af en samling af n elementer, der hver har en ikke-negativ heltalsnøgle, hvis maksimale værdi højst er k . I nogle beskrivelser af tællesortering antages det input, der skal sorteres, mere enkelt at være en sekvens af heltal i sig selv, men denne forenkling rummer ikke mange anvendelser af tællesortering. For eksempel, når den bruges som en underrutine i radix -sortering , er tasterne for hvert opkald til tællesortering individuelle cifre i større elementtaster; det ville ikke være tilstrækkeligt kun at returnere en sorteret liste over nøgletal, adskilt fra elementerne.

I applikationer som f.eks. I radix -sortering vil en grænse for den maksimale nøgleværdi k være kendt på forhånd og kan antages at være en del af input til algoritmen. Men hvis værdien af k ikke allerede er kendt, kan den som et første trin beregnes med et ekstra loop over dataene for at bestemme den maksimale nøgleværdi.

Outputtet er en matrix af de elementer, der er ordnet efter deres nøgler. På grund af dets anvendelse på radix -sortering skal tællesortering være en stabil sortering ; det vil sige, selvom to elementer deler den samme nøgle, skal deres relative position i output array og deres relative position i input array matche.

Pseudokode

I pseudokode kan algoritmen udtrykkes som: 

function CountingSort(input, k)
    
    count ← array of k + 1 zeros
    output ← array of same length as input
    
    for i = 0 to length(input) - 1 do
        j = key(input[i])
        count[j] += 1

    for i = 1 to k do
        count[i] += count[i - 1]

    for i = length(input) - 1 downto 0 do
        j = key(input[i])
        count[j] -= 1
        output[count[j]] = input[i]

    return output

Her inputer inputmatrixen, der skal sorteres, keyreturnerer den numeriske nøgle for hvert element i inputmatrixen, counter et hjælpematrix, der først bruges til at gemme antallet af elementer med hver nøgle og derefter (efter den anden loop) til at gemme positionerne, hvor elementer med hver nøgle skal placeres, ker den maksimale værdi af de ikke-negative nøgleværdier og outputer det sorterede output array.

Sammenfattende sløjfer algoritmen over elementerne i den første sløjfe og beregner et histogram over antallet af gange, hver nøgle forekommer i inputsamlingen. Derefter udfører den i den anden sløjfe en præfiks sumberegning på countfor for hver nøgle at bestemme positionsintervallet, hvor emnerne med denne nøgle skal placeres; dvs. nøgleelementer skal placeres startende på plads . Endelig i den tredje sløjfe sløjfer den over genstandene igen, men i omvendt rækkefølge og flytter hvert element til sin sorterede position i arrayet. count[]inputoutput

Den relative rækkefølge af genstande med lige nøgler bevares her; dvs. dette er en stabil slags .

Kompleksitetsanalyse

Fordi algoritmen kun bruger simple til sløjfer, uden rekursion eller subrutineopkald, er det ligetil at analysere. Initialiseringen af ​​tællearrayet og det andet for loop, der udfører en præfiks sum på tæller arrayet, gentager hver højst k + 1 gange og tager derfor O ( k ) tid. De to andre for sløjfer og initialiseringen af ​​output -arrayet tager hver især O ( n ) tid. Derfor er tiden for hele algoritmen summen af ​​tidspunkterne for disse trin, O ( n + k ) .

Fordi den bruger arrays med længden k + 1 og n , er algoritmens samlede pladsforbrug også O ( n + k ) . For problemforekomster, hvor den maksimale nøgleværdi er betydeligt mindre end antallet af emner, kan tællesortering være meget pladsbesparende, da den eneste lagring, den bruger andre end dens input- og output-arrays, er Count-arrayet, der bruger mellemrum O ( k ) .

Variantalgoritmer

Hvis hvert element, der skal sorteres, i sig selv er et heltal og også bruges som nøgle, kan den anden og tredje sløjfe af tællesortering kombineres; i den anden sløjfe, i stedet for at beregne den position, hvor emner med nøgle iskal placeres i output, skal du blot tilføje Count[i]kopier af nummeret itil output.

Denne algoritme kan også bruges til at eliminere dublerede nøgler ved at erstatte Countarrayet med en bitvektor, der gemmer a onefor en nøgle, der er til stede i input og en zerofor en nøgle, der ikke er til stede. Hvis elementerne derudover er selve heltallets nøgler, kan både anden og tredje sløjfe udelades fuldstændigt, og bitvektoren vil selv tjene som output, der repræsenterer værdierne som forskydninger for ikke- zeroposter, tilføjet til områdets laveste værdi. Således sorteres nøglerne, og dubletterne elimineres i denne variant bare ved at blive placeret i bitarrayet.

For data, hvor den maksimale nøglestørrelse er betydeligt mindre end antallet af dataelementer, kan tællesortering paralleliseres ved at opdele input i underarrays af omtrent lige stor størrelse, behandle hvert underarray parallelt for at generere et separat tællingsarray for hvert underarray, og derefter flette tælle -arrays. Når den bruges som en del af en parallel radix -sorteringsalgoritme, skal nøglestørrelsen (basis for radixrepræsentationen) vælges for at matche størrelsen på de delte underarrays. Enkelheden ved tællingssorteringsalgoritmen og dens anvendelse af det let paralleliserbare præfiks sum primitiv gør den også anvendelig i mere finkornede parallelle algoritmer.

Som beskrevet er tællesortering ikke en på stedet algoritme ; Selv hvis man ser bort fra tæller arrayet, har det brug for separate input og output arrays. Det er muligt at ændre algoritmen, så den placerer elementerne i sorteret rækkefølge inden for den samme matrix, der blev givet den som input, ved kun at bruge tælle -arrayet som hjælpelager; den ændrede in-place-version af tællesortering er imidlertid ikke stabil.

Historie

Selvom radixsortering i sig selv går meget længere tilbage, blev tællesortering og dens anvendelse på radixsortering begge opfundet af Harold H. Seward i 1954.

Referencer

eksterne links