streamalism.org

1. Oversigt

Sorteringsalgoritmer til almindelige formål som Merge Sort antager ikke noget om input, så de ikke kan slå O (n log n) i værste fald. Tællesortering har tværtimod en antagelse om input, som gør det til en lineær tidssorteringsalgoritme.

I denne vejledning vil vi blive bekendt med mekanikken i Counting Sort og derefter implementere den i Java.

2. Tællesortering

Tællesortering, i modsætning til de fleste klassiske sorteringsalgoritmer, sorterer ikke det givne input ved at sammenligne elementerne. I stedet, det antages, at inputelementerne er n heltal i området [0, k]. Hvornår k = O (n), så kører tællesorteren ind På) tid.

Vær opmærksom på, at vi ikke kan bruge tællesorteringen som en almindelig sorteringsalgoritme. Men når input er tilpasset denne antagelse, er det ret hurtigt!

2.1. Frekvensarray

Lad os antage, at vi skal sortere et input-arraymed værdier i området [0, 5]:

Først, vi skal tælle forekomsten af ​​hvert nummer i input-arrayet. Hvis vi repræsenterer optællingerne med array C, derefter C [i] repræsenterer antallet af antal jeg i inputmatrixen:

Da f.eks. 5 vises 3 gange i inputmatrixen, er værdien for indekset 5 lig med 3.

Nu givet arrayet C, vi skal bestemme, hvor mange elementer der er mindre end eller lig med hvert inputelement. For eksempel:

• Et element er mindre end eller lig med nul, eller med andre ord, der er kun en nulværdi, der er lig med C [0]
• To elementer er mindre end eller lig med et, hvilket er lig med C [0] + C [1]
• Fire værdier er mindre end eller lig med to, hvilket er lig med C [0] + C [1] + C [2]

Så hvis vi fortsætter med at beregne summeringen af n fortløbende elementer i C, vi kan vide, hvor mange elementer der er mindre end eller lig med antallet n-1 i input-arrayet. Under alle omstændigheder kan vi ved at anvende denne enkle formel opdatere C som følgende:

2.2. Algoritmen

Nu kan vi bruge hjælpearrayet C for at sortere inputmatrixen. Sådan fungerer tællesorteringen:

• Det gentager input-arrayet i omvendt rækkefølge
• For hvert element jeg, C [i] - 1 repræsenterer placeringen af ​​nummeret jeg i det sorterede array. Dette skyldes, at der er C [i] elementer mindre end eller lig med jeg
• Derefter mindskes det C [i] i slutningen af ​​hver runde

For at sortere prøveindgangsarrayet skal vi først starte med tallet 5, da det er det sidste element. Ifølge C [5], der er 11 elementer, der er mindre end eller lig med tallet 5.

Så 5 skal være det 11. element i det sorterede array, deraf indekset 10:

Da vi flyttede 5 til det sorterede array, skal vi nedtage C [5]. Næste element i den omvendte rækkefølge er 2. Da der er 4 elementer mindre end eller lig med 2, skal dette tal være det 4. element i den sorterede matrix:

På samme måde kan vi finde det rigtige sted for det næste element, som er 0:

Hvis vi bliver ved med at gentage omvendt og flytter hvert element passende, ville vi ende med noget som:

3. Tællesortering - Java-implementering

3.1. Beregning af frekvensarray

Først og fremmest, givet et input array af elementer og k, vi skulle beregne arrayet C:

int [] countElements (int [] input, int k) {int [] c = new int [k + 1]; Arrays. Udfyld (c, 0); for (int i: input) {c [i] + = 1; } for (int i = 1; i <c.længde; i ++) {c [i] + = c [i - 1]; } returnere c; }

Lad os opdele metodens signatur:

• input repræsenterer en række numre, vi skal sortere
• Det input array er en array med heltal i området [0, k] - så k repræsenterer det maksimale antal i input
• Returtypen er en række heltal, der repræsenterer C array

Og her er hvordan countElements metode fungerer:

• Først initialiserede vi C array. Som [0, k] -området indeholder k + 1 tal, vi opretter en matrix, der kan indeholde k + 1 numre
• Derefter for hvert nummer i input, vi beregner hyppigheden af ​​dette nummer
• Og endelig tilføjer vi sammenhængende elementer sammen for at vide, hvor mange elementer der er mindre end eller lig med et bestemt antal

Vi kan også kontrollere, at countElements metoden fungerer som forventet:

@Test ugyldigt antalElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected () {int k = 5; int [] input = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] c = CountingSort.countElements (input, k); int [] forventet = {1, 2, 4, 6, 8, 11}; assertArrayEquals (forventet, c); }

3.2. Sortering af inputmatrixen

Nu hvor vi kan beregne frekvensarrayet, skal vi være i stand til at sortere et hvilket som helst sæt sæt:

int [] sort (int [] input, int k) {int [] c = countElements (input, k); int [] sorteret = ny int [input.længde]; for (int i = input.length - 1; i> = 0; i--) {int current = input [i]; sorteret [c [nuværende] - 1] = strøm; c [nuværende] - = 1; } returneret sorteret; }

Sådan gør du sortere metode fungerer:

• For det første beregner den C array
• Derefter gentages det input array i omvendt rækkefølge og for hvert element i input, finder sit rette sted i det sorterede array. Det med element i input skulle være den C [i] th element i det sorterede array. Da Java-arrays er nulindekseret, er C [i] -1 indgang er C [i] th element - for eksempel sorteret [5] er det sjette element i den sorterede matrix
• Hver gang vi finder et match, reduceres det tilsvarende C [i] værdi

På samme måde kan vi kontrollere, at sortere metoden fungerer som forventet:

@Test ugyldigt sort_GivenAnArray_ShouldSortTheInputAsExpected () {int k = 5; int [] input = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] sorteret = CountingSort.sort (input, k); // Vores sorteringsalgoritme og Java'er skal returnere det samme resultat Arrays.sort (input); assertArrayEquals (input, sorteret); }

4. Genoptagelse af tællesorteringsalgoritmen

4.1. Kompleksitetsanalyse

De fleste klassiske sorteringsalgoritmer, som fusioneringssortering, sorterer ethvert givet input ved blot at sammenligne inputelementerne med hinanden. Denne type sorteringsalgoritmer er kendt som sammenligning sorterer. I værste fald bør sammenligningssorter mindst tage O(n log n) at sortere n elementer.

Counting Sort sorterer på den anden side ikke inputet ved at sammenligne inputelementerne, så det er tydeligvis ikke en sammenligningssorteringsalgoritme.

Lad os se, hvor meget tid det tager at sortere input:

• Det beregner C array i O (n + k) tid: Det gentager en gang et input array med størrelse n i På) og derefter gentager det C i Okay) - så det ville være O (n + k) i alt
• Efter beregning af C, den sorterer input ved at gentage input-arrayet og udføre et par primitive operationer i hver iteration. Så den faktiske sorteringsoperation tager På)

I alt tællesortering O (n + k) tid til at løbe:

O (n + k) + O (n) = O (2n + k) = O (n + k)

Hvis vi antager k = O (n), derefter sorterer tællesorteringsalgoritmen input i lineær tid. I modsætning til almindelige sorteringsalgoritmer antager sortering af sortering en antagelse om input og tager mindre end O(n log n) nedre grænse at udføre.

4.2. Stabilitet

For få øjeblikke siden lagde vi et par ejendommelige regler om mekanikken i tællesortering, men ryddede aldrig årsagen bag dem. For at være mere specifik:

• Hvorfor skal vi gentage input-arrayet omvendt?
• Hvorfor mindsker vi C [i] hver gang vi bruger det?

Lad os gentage fra begyndelsen for bedre at forstå den første regel. Antag, at vi skal sortere et simpelt array af heltal som følgende:

I den første iteration skal vi finde den sorterede placering til den første 1:

Så den første forekomst af nummer 1 får det sidste indeks i det sorterede array. Spring over tallet 0, lad os se, hvad der sker med den anden forekomst af nummer 1:

Udseenderækkefølgen for elementer med den samme værdi er forskellig i input og sorteret array, så algoritmen er ikke stabil, når vi gentager fra starten.

Hvad sker der, hvis vi ikke mindsker C [i] værdi efter hver brug? Lad os se:

Begge forekomster af nummer 1 får det sidste sted i det sorterede array. Så hvis vi ikke mindsker C [i] værdi efter hver brug, kan vi muligvis miste et par tal, mens vi sorterer dem!

5. Konklusion

I denne tutorial lærte vi først, hvordan Counting Sort fungerer internt. Derefter implementerede vi denne sorteringsalgoritme i Java og skrev et par tests for at verificere dens adfærd. Og endelig beviste vi, at algoritmen er en stabil sorteringsalgoritme med lineær tidskompleksitet.

Som sædvanlig er prøvekoderne tilgængelige på vores GitHub-projekt, så sørg for at tjekke det ud!