Counting Sort i Java

1. Oversikt

Generelle sorteringsalgoritmer som Merge Sort antar ikke inngangen, slik at de ikke kan slå O (n log n) i verste fall. Counting Sort har tvert imot en antagelse om inngangen som gjør det til en lineær tidssorteringsalgoritme.

I denne opplæringen skal vi bli kjent med mekanikken til Counting Sort og deretter implementere den i Java.

2. Counting Sort

Tellingsortering, i motsetning til de fleste klassiske sorteringsalgoritmer, sorterer ikke gitt input ved å sammenligne elementene. I stedet, det forutsetter at inngangselementene er n heltall i området [0, k]. Når k = O (n), da vil tellesortere kjøre inn På) tid.

Vær da oppmerksom på at vi ikke kan bruke tellesorteringen som en generell sorteringsalgoritme. Men når inngangen er i tråd med denne antagelsen, er det ganske raskt!

2.1. Frequency Array

La oss anta at vi skal sortere en inngangsoppstillingmed verdier i [0, 5] -området:

Først, vi bør telle forekomsten av hvert nummer i inndata-arrayet. Hvis vi representerer tellinger med matrise C, deretter C [i] representerer antallfrekvensen Jeg i inngangsoppstillingen:

For eksempel, siden 5 vises 3 ganger i inngangsruten, er verdien for indeksen 5 lik 3.

Nå gitt matrisen C, vi bør bestemme hvor mange elementer som er mindre enn eller like hvert inngangselement. For eksempel:

Ett element er mindre enn eller lik null, eller med andre ord, det er bare en nullverdi, som er lik C [0]
To elementer er mindre enn eller lik ett, som er lik C [0] + C [1]
Fire verdier er mindre enn eller lik to, som er lik C [0] + C [1] + C [2]

Så hvis vi fortsetter å beregne summeringen av n påfølgende elementer i C, vi kan vite hvor mange elementer som er mindre enn eller like antall n-1 i inngangsoppstillingen. Uansett, ved å bruke denne enkle formelen kan vi oppdatere C som følgende:

2.2. Algoritmen

Nå kan vi bruke hjelpearrangementet C for å sortere inngangsmatrisen. Slik fungerer tellesorteringen:

Det gjentar inndata-arrayet i omvendt retning
For hvert element Jeg, C [i] - 1 representerer plasseringen av nummeret Jeg i den sorterte matrisen. Dette er på grunn av det faktum at det er C [i] elementer mindre enn eller lik Jeg
Deretter reduseres den C [i] på slutten av hver runde

For å sortere inngangsruten til prøven, bør vi først starte med tallet 5, siden det er det siste elementet. I følge C [5], det er 11 elementer som er mindre enn eller lik tallet 5.

Så, 5 skal være det 11. elementet i den sorterte matrisen, derav indeksen 10:

Siden vi flyttet 5 til den sorterte matrisen, bør vi redusere C [5]. Neste element i omvendt rekkefølge er 2. Siden det er 4 elementer mindre enn eller lik 2, bør dette tallet være det fjerde elementet i den sorterte matrisen:

På samme måte kan vi finne det rette stedet for neste element som er 0:

Hvis vi fortsetter å gjenta i omvendt retning og flytter hvert element riktig, vil vi ende opp med noe som:

3. Counting Sort - Java Implementation

3.1. Beregning av frekvensoppsettet

Først og fremst, gitt et inngangssett av elementer og k, vi skal beregne matrisen C:

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

La oss bryte ned metodesignaturen:

inngang representerer en rekke tall vi skal sortere
De inngang array er en array med heltall i området [0, k] - så k representerer maksimalt antall i inngang
Returtypen er en rekke heltall som representerer C array

Og her er hvordan countElements metoden fungerer:

Først initialiserte vi C array. Som [0, k] -området inneholder k + 1 tall, lager vi en matrise som kan inneholde k + 1 tall
Deretter for hvert tall i inngang, vi beregner frekvensen til det tallet
Og til slutt legger vi sammen påfølgende elementer for å vite hvor mange elementer som er mindre enn eller lik et bestemt tall

Vi kan også bekrefte at countElements metoden fungerer som forventet:

@Test ugyldige countElements_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 av Input Array

Nå som vi kan beregne frekvensoppsettet, bør vi kunne sortere et gitt sett med tall:

int [] sort (int [] input, int k) {int [] c = countElements (input, k); int [] sortert = ny int [input.length]; for (int i = input.length - 1; i> = 0; i--) {int current = input [i]; sortert [c [gjeldende] - 1] = gjeldende; c [gjeldende] - = 1; } retur sortert; }

Slik gjør du sortere metoden fungerer:

For det første beregner den C array
Deretter itererer det inngang array i omvendt retning og for hvert element i inngang, finner sitt rette sted i den sorterte matrisen. De ith element i inngang skal være C [i] th element i den sorterte matrisen. Siden Java-matriser er nullindeksert, blir C [i] -1 oppføringen er C [i] th element - for eksempel sortert [5] er det sjette elementet i den sorterte matrisen
Hver gang vi finner en kamp, reduseres den tilsvarende C [i] verdi

På samme måte kan vi verifisere at sortere metoden fungerer som forventet:

@Test ugyldig sort_GivenAnArray_ShouldSortTheInputAsExpected () {int k = 5; int [] input = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] sorted = CountingSort.sort (input, k); // Vår sorteringsalgoritme og Java skal returnere det samme resultatet Arrays.sort (input); assertArrayEquals (input, sorted); }

4. Gjennomgang av tellingssorteringsalgoritmen

4.1. Kompleksitetsanalyse

De fleste klassiske sorteringsalgoritmer, som flettesortering, sorterer hvilken som helst gitt inngang ved å bare sammenligne inngangselementene med hverandre. Denne typen sorteringsalgoritmer er kjent som sammenligning sorterer. I verste fall bør sammenligningssorter ta minst O(n log n) Å sortere n elementer.

Counting Sort, derimot, sorterer ikke inngangen ved å sammenligne inngangselementene, så det er tydeligvis ikke en sammenligningssorteringsalgoritme.

La oss se hvor mye tid det tar å sortere inngangen:

Den beregner C rekke i O (n + k) tid: Det en gang itererer et inngangssett med størrelse n i På) og deretter gjentar det C i O (k) - slik at det ville være O (n + k) totalt
Etter å ha beregnet C, den sorterer inngangen ved å gjenta inngangsmatrisen og utføre noen få primitive operasjoner i hver iterasjon. Så den faktiske sorteringsoperasjonen tar På)

Totalt tar tellesortering O (n + k) tid til å løpe:

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

Hvis vi antar k = O (n), deretter sorterer sorteringsalgoritmen inngangen i lineær tid. I motsetning til generelle sorteringsalgoritmer, antar telling sorter en antagelse om inngangen og tar mindre enn O(n log n) nedre grense for å utføre.

4.2. Stabilitet

For noen øyeblikk siden la vi noen særegne regler om mekanikken til å telle sortering, men ryddet aldri årsaken bak dem. For å være mer presis:

Hvorfor skal vi gjenta inngangsoppstillingen i omvendt retning?
Hvorfor vi reduserer C [i] hver gang vi bruker det?

La oss gjenta fra begynnelsen for å forstå den første regelen bedre. Anta at vi skal sortere et enkelt utvalg av heltall slik:

I den første iterasjonen bør vi finne den sorterte plasseringen for den første 1:

Så den første forekomsten av nummer 1 får den siste indeksen i den sorterte matrisen. Hopp over tallet 0, la oss se hva som skjer med den andre forekomsten av nummer 1:

Utseende rekkefølge for elementer med samme verdi er forskjellig i inngangs- og sortert matrise, så algoritmen er ikke stabil når vi itererer fra begynnelsen.

Hva skjer hvis vi ikke reduserer C [i] verdi etter hver bruk? La oss se:

Begge forekomster av nummer 1 får siste plass i den sorterte matrisen. Så hvis vi ikke reduserer C [i] verdi etter hver bruk, kan vi potensielt miste noen få tall mens vi sorterer dem!

5. Konklusjon

I denne veiledningen lærte vi først hvordan Counting Sort fungerer internt. Så implementerte vi denne sorteringsalgoritmen i Java og skrev noen få tester for å verifisere oppførselen. Og til slutt beviste vi at algoritmen er en stabil sorteringsalgoritme med lineær tidskompleksitet.

Eksempelkodene er som vanlig tilgjengelige på GitHub-prosjektet vårt, så sørg for å sjekke det ut!

streamalism.org