In deze tutorial leer je hoe radix sorteren werkt. Ook vindt u werkende voorbeelden van radix-sortering in C, C ++, Java en Python.
Radix Sort is een sorteertechniek dat de elementen door eerst de individuele cijfers van dezelfde groepering sorteert plaatswaarde . Sorteer de elementen vervolgens op volgorde van oplopende / afnemende volgorde.
Stel dat we een reeks van 8 elementen hebben. Eerst zullen we elementen sorteren op basis van de waarde van de eenheidsplaats. Vervolgens sorteren we elementen op basis van de waarde van de tiende plaats. Dit proces gaat door tot de laatste belangrijke plaats.
Laat de eerste array zijn (121, 432, 564, 23, 1, 45, 788). Het is gesorteerd op radix-sortering zoals weergegeven in de onderstaande afbeelding.
Werking van Radix Sort
Ga alsjeblieft door de telsortering voordat je dit artikel leest, want telsortering wordt gebruikt als een tussenliggende sortering in radix-sortering.
Hoe Radix Sort werkt?
- Zoek het grootste element in de array, dwz max. Laat
Xhet aantal cijfers zijnmax.Xwordt berekend omdat we alle belangrijke plaatsen van alle elementen moeten doorlopen.
In deze array(121, 432, 564, 23, 1, 45, 788)hebben we het grootste nummer 788. Het heeft 3 cijfers. Daarom moet de lus naar honderden plaatsen gaan (3 keer). - Ga nu een voor een door elke belangrijke plaats.
Gebruik een stabiele sorteertechniek om de cijfers op elke belangrijke plaats te sorteren. Hiervoor hebben we telsortering gebruikt.
Sorteer de elementen op basis van de cijfers van de eenheidsplaats (X=0).
Counting sort gebruiken om elementen te sorteren op basis van eenheidsplaats - Sorteer nu de elementen op basis van cijfers op tientallen plaatsen.
Sorteer elementen op basis van tientallen plaatsen - Sorteer ten slotte de elementen op basis van de cijfers op honderden plaatsen.
Sorteer elementen op basis van honderden plaatsen
Radix-sorteeralgoritme
radixSort (array) d <- maximum aantal cijfers in het grootste element maak d-emmers van grootte 0-9 voor i <- 0 tot d sorteer de elementen op de plaatscijfers met behulp van countingSort countingSort (array, d) max <- vind grootste element onder dde plaatselementen initialiseren telarray met allemaal nullen voor j <- 0 om de grootte te bepalen vind het totale aantal van elk uniek cijfer op de dde plaats van elementen en sla het aantal op bij jde index in telarray voor i <- 1 tot max. vind de cumulatieve som en sla het op in de telarray zelf voor j <- grootte teruggebracht tot 1 herstel de elementen naar array verminder het aantal van elk element hersteld met 1
Python, Java en C / C ++ voorbeelden
Python Java C C ++ # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)
// Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
// Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
Complexiteit
Omdat radix-sortering een niet-vergelijkend algoritme is, heeft het voordelen ten opzichte van vergelijkende sorteeralgoritmen.
Voor de radix-sortering die telsortering gebruikt als een tussenliggende stabiele sortering, is de tijdcomplexiteit O(d(n+k)).
Hier dis de nummercyclus en O(n+k)is de tijdcomplexiteit van telsortering.
Radix-sortering heeft dus een lineaire tijdcomplexiteit die beter is dan O(nlog n)vergelijkbare sorteeralgoritmen.
Als we getallen met zeer grote cijfers nemen of het aantal andere basen zoals 32-bits en 64-bits getallen, dan kan het in lineaire tijd werken, maar de tussenliggende sortering neemt veel ruimte in beslag.
Dit maakt radix sorteerruimte inefficiënt. Dit is de reden waarom deze soort niet wordt gebruikt in softwarebibliotheken.
Radix Sort-toepassingen
Radix sort is geïmplementeerd in
- DC3-algoritme (Kärkkäinen-Sanders-Burkhardt) bij het maken van een suffix-array.
- plaatsen met nummers in grote reeksen.
