streamalism.org

1. Inleiding

In deze tutorial leren we Radix Sort kennen, analyseren we de prestaties en bekijken we de implementatie ervan.

Hier richten we ons op het gebruik van Radix Sort om gehele getallen te sorteren, maar het is niet beperkt tot alleen getallen. We kunnen het gebruiken om andere typen te sorteren, zoals Draad, te.

Om het simpel te houden, gaan we ons concentreren op het decimale systeem waarin de getallen worden uitgedrukt in grondtal (radix) 10.

2. Algoritme overzicht

Radix sort is een sorteeralgoritme dat getallen sorteert op basis van de positie van hun cijfers. In feite gebruikt het de plaatswaarde van de cijfers in een getal. In tegenstelling tot de meeste andere sorteeralgoritmen, zoals samenvoegen sorteren, invoegen sorteren, bellen sorteren, worden de getallen niet vergeleken.

Radix sorteren gebruikt een stabiel sorteeralgoritme als een subroutine om de cijfers te sorteren. We hebben hier een variatie van telsortering als een subroutine gebruikt die de radix gebruikt om de cijfers op elke positie te sorteren. Counting sort is een stabiel sorteeralgoritme en werkt in de praktijk goed.

Radix sorteren werkt door cijfers te sorteren van het minst significante cijfer (LSD) naar het meest significante cijfer (MSD). We kunnen Radix-sortering ook implementeren om cijfers van MSD te verwerken.

3. Een snel voorbeeld

Laten we eens kijken hoe het werkt met een voorbeeld. Laten we eens kijken naar de volgende array:

Iteratie 1:

We sorteren deze array door cijfers van LSD te verwerken en naar MSD te gaan.

Dus laten we beginnen met de cijfers op één plaats:

Na de eerste iteratie ziet de array er nu als volgt uit:

Merk op dat de nummers zijn gesorteerd volgens de cijfers op een plaats.

Iteratie 2:

Laten we verder gaan met de cijfers op de plaats van tien:

Nu ziet de array er als volgt uit:

We zien dat het getal 7 de eerste positie in de array heeft ingenomen, omdat er geen cijfer op de plaats van de tienen staat. We zouden dit ook kunnen beschouwen als een 0 op de tientallen.

Iteratie 3:

Laten we verder gaan met de cijfers in de honderden positie:

Na deze iteratie ziet de array er als volgt uit:

En het algoritme stopt hier, met alle elementen gesorteerd.

4. Implementatie

Laten we nu eens kijken naar de implementatie.

void sort (int [] nummers) {int maximumNumber = findMaximumNumberIn (nummers); int numberOfDigits = berekenNumberOfDigitsIn (maximumNummer); int placeValue = 1; while (numberOfDigits--> 0) {applyCountingSortOn (numbers, placeValue); placeValue * = 10; }}

Het algoritme werkt door het maximale aantal in de array te achterhalen en vervolgens de lengte te berekenen. Deze stap helpt ons om ervoor te zorgen dat we de subroutine voor elke plaatswaarde uitvoeren.

In de array, [7, 37, 68, 123, 134, 221, 387, 468, 769], het maximale aantal is 769 en de lengte is 3.

Dus we herhalen en passen de subroutine driemaal toe op de cijfers in elke positie:

void applyCountingSortOn (int [] numbers, int placeValue) {int range = 10 // decimaal systeem, getallen van 0-9 // ... // bereken de frequentie van cijfers voor (int i = 0; i <length; i ++ ) {int digit = (numbers [i] / placeValue)% bereik; frequentie [cijfer] ++; } voor (int i = 1; i = 0; i--) {int digit = (numbers [i] / placeValue)% bereik; gesorteerdeValues ​​[frequentie [cijfer] - 1] = getallen [i]; frequentie [cijfer] -; } System.arraycopy (resultaat, 0, getallen, 0, lengte); }

In de subroutine hebben we de radix gebruikt (bereik) om het voorkomen van elk cijfer te tellen en de frequentie ervan te verhogen. Dus elke bak in het bereik van 0 tot 9 heeft een bepaalde waarde op basis van de frequentie van cijfers. Vervolgens gebruiken we de frequentie om elk element in de array te positioneren. Dit helpt ons ook om de ruimte die nodig is om de array te sorteren, te minimaliseren.

Laten we nu onze methode testen:

@Test openbare leegte gegevenUnsortedArray_whenRadixSort_thenArraySorted () {int [] getallen = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort (cijfers); int [] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals (numbersSorted, numbers); }

5. Radix sorteren versus tellen sorteren

In de subroutine is de lengte van de frequentie matrix is ​​10 (0-9). In het geval van Counting Sort gebruiken we niet de bereik. De lengte van de frequentie array is het maximale aantal in de array + 1. We verdelen ze dus niet in bakken, terwijl Radix Sort de bakken gebruikt om te sorteren.

Counting Sort is behoorlijk efficiënt als de lengte van de array niet veel kleiner is dan de maximale waarde in de array, terwijl Radix Sort grotere waarden in de array mogelijk maakt.

6. Complexiteit

De prestaties van Radix Sort zijn afhankelijk van het stabiele sorteeralgoritme dat is gekozen om de cijfers te sorteren.

Hier hebben we de Radix Sort gebruikt om een ​​reeks van n nummers in basis b. In ons geval is de basis 10. We hebben de Counting Sort toegepast d keer waar d staat voor het aantal cijfers. Dus de tijdcomplexiteit van Radix Sort wordt O (d * (n + b)).

De complexiteit van de ruimte is O (n + b) aangezien we hier een variant van Counting Sort als subroutine hebben gebruikt.

7. Conclusie

In dit artikel hebben we het Radix-sorteeralgoritme beschreven en geïllustreerd hoe het moet worden geïmplementeerd.

Zoals gewoonlijk zijn de code-implementaties beschikbaar op Github.