Tellen Sorteren in Java

1. Overzicht

Sorteeralgoritmen voor algemene doeleinden, zoals Merge Sort, gaan niet uit van de invoer, dus ze kunnen de O (n log n) in het slechtste geval. Counting Sort daarentegen heeft een aanname over de invoer waardoor het een lineair tijd-sorteeralgoritme is.

In deze tutorial gaan we kennis maken met de mechanica van de Counting Sort en deze vervolgens in Java implementeren.

2. Tellen sorteren

Tellen sorteren, in tegenstelling tot de meeste klassieke sorteeralgoritmen, sorteert de gegeven invoer niet door de elementen te vergelijken. In plaats daarvan, het veronderstelt dat de invoerelementen dat zijn n gehele getallen in het bereik [0, k]. Wanneer k = O (n), dan zal de tellende sortering binnenkomen Aan) tijd.

Houd er dus rekening mee dat we de telsortering niet kunnen gebruiken als een algemeen sorteeralgoritme. Wanneer de invoer echter is uitgelijnd met deze aanname, is het behoorlijk snel!

2.1. Frequentie-array

Stel dat we een invoerarray gaan sorterenmet waarden in het bereik [0, 5]:

Eerste, we moeten het voorkomen van elk nummer in de invoerarray tellen. Als we de tellingen vertegenwoordigen met array C, dan C [i] vertegenwoordigt de frequentie van nummer ik in de invoerarray:

Omdat 5 bijvoorbeeld driemaal voorkomt in de invoerarray, is de waarde voor de index 5 gelijk aan 3.

Nu gezien de array C, we moeten bepalen hoeveel elementen kleiner dan of gelijk zijn aan elk invoerelement. Bijvoorbeeld:

Eén element is kleiner dan of gelijk aan nul, of met andere woorden, er is maar één nulwaarde, die gelijk is aan C [0]
Twee elementen zijn kleiner dan of gelijk aan één, die gelijk is aan C [0] + C [1]
Vier waarden zijn kleiner dan of gelijk aan twee, wat gelijk is aan C [0] + C [1] + C [2]

Dus als we de sommatie van n opeenvolgende elementen in C, we kunnen weten hoeveel elementen kleiner zijn dan of gelijk zijn aan getal n-1 in de invoerarray. Hoe dan ook, door deze eenvoudige formule toe te passen, kunnen we het C als het volgende:

2.2. Het algoritme

Nu kunnen we de hulparray gebruiken C om de invoerarray te sorteren. Hier is hoe de telsortering werkt:

Het herhaalt de invoerarray in omgekeerde volgorde
Voor elk element ik, C [i] - 1 vertegenwoordigt de locatie van het nummer ik in de gesorteerde array. Dit komt door het feit dat er C [i] elementen kleiner dan of gelijk aan ik
Vervolgens verlaagt het de C [i] aan het einde van elke ronde

Om de voorbeeldinvoerarray te sorteren, moeten we eerst beginnen met het cijfer 5, aangezien dit het laatste element is. Volgens C [5], er zijn 11 elementen die kleiner zijn dan of gelijk zijn aan het getal 5.

Dus 5 zou het 11e element in de gesorteerde array moeten zijn, vandaar de index 10:

Omdat we 5 naar de gesorteerde array hebben verplaatst, moeten we de C [5]. Het volgende element in de omgekeerde volgorde is 2. Aangezien er 4 elementen kleiner dan of gelijk aan 2 zijn, zou dit nummer het 4e element in de gesorteerde array moeten zijn:

Evenzo kunnen we de juiste plek vinden voor het volgende element dat 0 is:

Als we in omgekeerde volgorde blijven herhalen en elk element op de juiste manier verplaatsen, zouden we eindigen met zoiets als:

3. Counting Sort - Java-implementatie

3.1. Berekenen van de frequentie-array

Ten eerste, gegeven een invoerarray van elementen en de k, we zouden de array moeten berekenen C:

int [] countElements (int [] invoer, int k) {int [] c = nieuwe int [k + 1]; Arrays.fill (c, 0); voor (int i: input) {c [i] + = 1; } for (int i = 1; i <c.length; i ++) {c [i] + = c [i - 1]; } retourneer c; }

Laten we de handtekening van de methode uitsplitsen:

invoer vertegenwoordigt een reeks getallen die we gaan sorteren
De invoer array is een array van gehele getallen in het bereik van [0, k] - zo k staat voor het maximale aantal in de invoer
Het retourtype is een reeks gehele getallen die de C array

En hier is hoe de countElements methode werkt:

Eerst hebben we het C array. Omdat het bereik [0, k] bevat k + 1 getallen, we maken een array die k + 1 nummers
Vervolgens voor elk nummer in de invoer, we berekenen de frequentie van dat aantal
En tot slot voegen we opeenvolgende elementen bij elkaar om te weten hoeveel elementen kleiner dan of gelijk zijn aan een bepaald getal

We kunnen ook verifiëren dat het countElements methode werkt zoals verwacht:

@Test ongeldig 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 [] verwacht = {1, 2, 4, 6, 8, 11}; assertArrayEquals (verwacht, c); }

3.2. De invoerarray sorteren

Nu we de frequentiematrix kunnen berekenen, zouden we elke gegeven reeks getallen moeten kunnen sorteren:

int [] sort (int [] invoer, int k) {int [] c = countElements (invoer, k); int [] gesorteerd = nieuwe int [input.length]; for (int i = input.length - 1; i> = 0; i--) {int current = input [i]; gesorteerd [c [huidig] - 1] = huidig; c [huidig] - = 1; } terug gesorteerd; }

Hier is hoe de soort methode werkt:

Ten eerste berekent het de C array
Vervolgens herhaalt het de invoer array omgekeerd en voor elk element in de invoer, vindt de juiste plek in de gesorteerde array. De ith element in het invoer zou de C [i] th element in de gesorteerde array. Aangezien Java-arrays nul-geïndexeerd zijn, is de C [i] -1 vermelding is de C [i] th element - bijvoorbeeld gesorteerd [5] is het zesde element in de gesorteerde array
Elke keer dat we een overeenkomst vinden, verlaagt het de corresponderende C [i] waarde

Evenzo kunnen we verifiëren dat het soort methode werkt zoals verwacht:

@Test ongeldig sort_GivenAnArray_ShouldSortTheInputAsExpected () {int k = 5; int [] input = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] gesorteerd = CountingSort.sort (invoer, k); // Ons sorteeralgoritme en Java's zouden hetzelfde resultaat moeten retourneren. Arrays.sort (input); assertArrayEquals (invoer, gesorteerd); }

4. Het algoritme voor tellen en sorteren opnieuw bekijken

4.1. Complexiteitsanalyse

De meeste klassieke sorteeralgoritmen, zoals samenvoegsortering, sorteren elke invoer door de invoerelementen met elkaar te vergelijken. Dit soort sorteeralgoritmen staan bekend als vergelijking sorteert. In het ergste geval moeten vergelijkingssoorten ten minste O duren(n log n) sorteren n elementen.

Counting Sort, aan de andere kant, sorteert de invoer niet door de invoerelementen te vergelijken, dus het is duidelijk geen vergelijkingssorteeralgoritme.

Laten we eens kijken hoeveel tijd het kost om de invoer te sorteren:

Het berekent de C array in O (n + k) tijd: het herhaalt een keer een invoerarray met de grootte n in Aan) en herhaalt vervolgens het C in OK) - dus dat zou zijn O (n + k) in totaal
Na het berekenen van de C, het sorteert de invoer door de invoerarray te herhalen en een paar primitieve bewerkingen uit te voeren in elke iteratie. Dus de daadwerkelijke sorteerbewerking duurt Aan)

In totaal duurt het tellen van de sortering O (n + k) tijd om te rennen:

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

Als we aannemen k = O (n), dan sorteert het tellen-sorteeralgoritme de invoer in lineaire tijd. In tegenstelling tot algemene sorteeralgoritmen, doet telsortering een aanname over de invoer en kost minder dan de O(n log n) ondergrens om uit te voeren.

4.2. Stabiliteit

Een paar ogenblikken geleden hebben we een paar eigenaardige regels opgesteld over de mechanica van het tellen, maar we hebben nooit de reden erachter gewist. Om specifieker te zijn:

Waarom zouden we de invoerarray in omgekeerde volgorde herhalen?
Waarom we de C [i] elke keer dat we het gebruiken?

Laten we vanaf het begin herhalen om de eerste regel beter te begrijpen. Stel dat we een eenvoudige reeks gehele getallen gaan sorteren, zoals de volgende:

In de eerste iteratie moeten we de gesorteerde locatie voor de eerste 1 vinden:

Dus de eerste keer dat nummer 1 voorkomt, krijgt de laatste index in de gesorteerde array. Laten we het nummer 0 overslaan, laten we eens kijken wat er gebeurt met de tweede keer dat nummer 1 voorkomt:

De weergavevolgorde van elementen met dezelfde waarde is anders in de invoer- en gesorteerde array, dus het algoritme is niet stabiel wanneer we vanaf het begin itereren.

Wat gebeurt er als we de C [i] waarde na elk gebruik? Laten we kijken:

Beide exemplaren van nummer 1 krijgen de laatste plaats in de gesorteerde array. Dus als we de C [i] waarde na elk gebruik, kunnen we mogelijk een paar getallen verliezen tijdens het sorteren!

5. Conclusie

In deze tutorial hebben we eerst geleerd hoe de Counting Sort intern werkt. Vervolgens hebben we dit sorteeralgoritme in Java geïmplementeerd en een paar tests geschreven om het gedrag ervan te verifiëren. En tot slot hebben we bewezen dat het algoritme een stabiel sorteeralgoritme is met lineaire tijdcomplexiteit.

Zoals gewoonlijk zijn de voorbeeldcodes beschikbaar op ons GitHub-project, dus zorg ervoor dat je het bekijkt!

streamalism.org