Sorteer Radix is een lineair sorteeralgoritme dat elementen sorteert door ze cijfer voor cijfer te verwerken. Het is een efficiënt sorteeralgoritme voor gehele getallen of tekenreeksen met sleutels van vaste grootte.
In plaats van elementen rechtstreeks te vergelijken, verdeelt Radix Sort de elementen in buckets op basis van de waarde van elk cijfer. Door de elementen herhaaldelijk te sorteren op hun significante cijfers, van de minst significante tot de meest significante, bereikt Radix Sort de uiteindelijke gesorteerde volgorde.
Radix sorteeralgoritme
Het sleutelidee achter Radix Sort is het exploiteren van het concept van plaatswaarde. Er wordt van uitgegaan dat het sorteren van getallen cijfer voor cijfer uiteindelijk zal resulteren in een volledig gesorteerde lijst. Radix Sorteren kan worden uitgevoerd met behulp van verschillende variaties, zoals Radix Sorteren met Least Significant Digit (LSD) of Radix Sorteren met Meest Significante Cijfers (MSD).
Hoe werkt het Radix sorteeralgoritme?
Om radixsortering uit te voeren op de array [170, 45, 75, 90, 802, 24, 2, 66] volgen we deze stappen:
Hoe werkt het Radix sorteeralgoritme | Stap 1
Stap 1: Zoek het grootste element in de array, namelijk 802. Het heeft drie cijfers, dus we zullen dit drie keer herhalen, één keer voor elke significante plaats.
Stap 2: Sorteer de elementen op basis van de eenheidscijfers (X=0). We gebruiken een stabiele sorteertechniek, zoals telsortering, om de cijfers op elke belangrijke plaats te sorteren.
css voor vetgedruktSortering op basis van de eenheidsplaats:
- Voer een telsortering uit op de array op basis van de cijfers van de eenheidsplaats.
- De gesorteerde array op basis van de eenheidsplaats is [170, 90, 802, 2, 24, 45, 75, 66].
Hoe werkt het Radix sorteeralgoritme | Stap 2
Stap 3: Sorteer de elementen op basis van de cijfers van de tientallen.
Sortering op basis van de tienenplaats:
- Voer een telsortering uit op de array op basis van de cijfers van de tientallen.
- De gesorteerde array op basis van de tientallen is [802, 2, 24, 45, 66, 170, 75, 90].
Hoe werkt het Radix sorteeralgoritme | Stap 3
Stap 4: Sorteer de elementen op basis van de honderden cijfers.
Sortering op basis van de honderdenplaatsen:
- Voer een telsortering uit op de array op basis van de cijfers van de honderden plaatsen.
- De gesorteerde array op basis van de honderdtallen is [2, 24, 45, 66, 75, 90, 170, 802].
Hoe werkt het Radix sorteeralgoritme | Stap 4
Stap 5: De array wordt nu in oplopende volgorde gesorteerd.
vlc youtube-video's downloadenDe uiteindelijk gesorteerde array met radix-sortering is [2, 24, 45, 66, 75, 90, 170, 802].
Hoe werkt het Radix sorteeralgoritme | Stap 5
Hieronder vindt u de implementatie van de bovenstaande illustraties:
C++ // C++ implementation of Radix Sort #include using namespace std; // A utility function to get maximum // value in arr[] int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arr[i]; retour MX; } // Een functie om een soort arr[] te tellen // volgens het cijfer // weergegeven door exp. void countSort(int arr[], int n, int exp) {// Uitvoerarray int output[n]; int ik, tel[10] = { 0 }; // Bewaar het aantal keren dat het voorkomt // in count[] voor (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] // now contains actual position // of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; ik--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; aantal[(arr[i] / exp) % 10]--; } // Kopieer de uitvoerarray naar arr[], // zodat arr[] nu gesorteerde // getallen bevat volgens het huidige cijfer voor (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] // of size n using Radix Sort void radixsort(int arr[], int n) { // Find the maximum number to // know number of digits int m = getMax(arr, n); // Do counting sort for every digit. // Note that instead of passing digit // number, exp is passed. exp is 10^i // where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Een hulpprogrammafunctie om een array void print(int arr[], int n) { for (int i = 0; i< n; i++) cout << arr[i] << ' '; } // Driver Code int main() { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call radixsort(arr, n); print(arr, n); return 0; }> Java // Radix sort Java implementation import java.io.*; import java.util.*; class Radix { // A utility function to get maximum value in arr[] static int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arr[i]; retour MX; } // Een functie om het soort arr[] te tellen volgens // het cijfer dat wordt weergegeven door exp. static void countSort(int arr[], int n, int exp) { int output[] = nieuwe int[n]; // uitvoerarray int i; int aantal[] = nieuwe int[10]; Arrays.fill(telling, 0); // Bewaar het aantal voorvallen in count[] voor (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; ik--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; aantal[(arr[i] / exp) % 10]--; } // Kopieer de uitvoerarray naar arr[], zodat arr[] nu // gesorteerde getallen bevat volgens het huidige // cijfer voor (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of // size n using Radix Sort static void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Een hulpprogrammafunctie voor het afdrukken van een array static void print(int arr[], int n) { for (int i = 0; i< n; i++) System.out.print(arr[i] + ' '); } // Main driver method public static void main(String[] args) { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.length; // Function Call radixsort(arr, n); print(arr, n); } }> Python3 # Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = arr[i] // exp1 count[index % 10] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1, 10): count[i] += count[i - 1] # Build the output array i = n - 1 while i>= 0: index = arr[i] // exp1 output[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # De uitvoerarray kopiëren naar arr[] , # zodat arr nu gesorteerde getallen bevat i = 0 voor i in bereik(0, len(arr)): arr[i] = output[i] # Werkwijze Radix Sort def radixSort(arr): # Zoek het maximum getal om te weten aantal cijfers max1 = max(arr) # Voer een telsortering uit voor elk cijfer. Merk op dat in plaats van # van het passerende cijfer, exp wordt doorgegeven. exp is 10^i # waarbij i het huidige cijfer is exp = 1 terwijl max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Stuurprogrammacode arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Functieaanroep radixSort(arr) voor i in bereik(len(arr)): print(arr[i], end=' ') # Deze code is bijgedragen door Mohit Kumra # Bewerkt door Patrick Gallagher>
C# // C# implementation of Radix Sort using System; class GFG { public static int getMax(int[] arr, int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arr[i]; retour MX; } // Een functie om het soort arr[] te tellen volgens // het cijfer dat wordt weergegeven door exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // uitvoerarray int i; int[] aantal = nieuwe int[10]; // initialiseren van alle elementen van het tellen naar 0 voor (i = 0; i< 10; i++) count[i] = 0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; ik--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; aantal[(arr[i] / exp) % 10]--; } // Kopieer de uitvoerarray naar arr[], zodat arr[] nu // gesorteerde getallen bevat volgens het huidige // cijfer voor (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort public static void radixsort(int[] arr, int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Een hulpprogrammafunctie om een array public static void print(int[] arr, int n) {for (int i = 0; i) af te drukken< n; i++) Console.Write(arr[i] + ' '); } // Driver Code public static void Main() { int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; // Function Call radixsort(arr, n); print(arr, n); } // This code is contributed by DrRoot_ }> Javascript // Radix sort JavaScript implementation 'use strict'; // A utility function to get maximum value in arr[] function getMax(arr) { const length = arr.length; let mx = arr[0]; for (let i = 1; i < length; i++) { if (arr[i]>mx) mx = arr[i]; } return mx; } // Een functie om het soort arr[] te tellen volgens // het cijfer dat wordt weergegeven door exp. functie countSort(arr, exp) { const lengte = arr.lengte; laat uitvoer = Array(lengte); // uitvoerarray laat tellen = Array(10).fill(0, 0); // Bewaar het aantal keren dat het voorkomt in count[] voor (laat i = 0; i< length; i++) { const digit = Math.floor(arr[i] / exp) % 10; count[digit]++; } // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (let i = 1; i < 10; i++) { count[i] += count[i - 1]; } // Build the output array for (let i = length - 1; i>= 0; i--) { const cijfer = Math.floor(arr[i] / exp) % 10; uitvoer[aantal[cijfer] - 1] = arr[i]; tel[cijfer]--; } retourneer uitvoer; } // De belangrijkste functie die arr[] sorteert met behulp van de Radix Sort-functie radixSort(arr) {// Vind het maximale aantal om het aantal cijfers te kennen const maxNumber = getMax(arr); // Maak een ondiepe kopie waarin de gesorteerde waarden behouden blijven, let sortArr = [...arr]; // Voer een telsortering uit voor elk cijfer. Merk op dat // in plaats van een cijfer door te geven, exp wordt doorgegeven. // exp is 10^i waarbij i het huidige cijfer is voor (laat exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) {// Haal de telling op sort iteratie const sortedIteration = countSort(sortedArr , exp); gesorteerdArr = gesorteerdIteratie; } retourneert gesorteerdArr; } /*Bestuurderscode*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Functie-aanroep const gesorteerdArr = radixSort(arr); console.log(gesorteerde Arr.join(' ')); // Deze code is bijgedragen door beeduhboodee> PHP // PHP implementation of Radix Sort // A function to do counting sort of arr[] // according to the digit represented by exp. function countSort(&$arr, $n, $exp) { $output = array_fill(0, $n, 0); // output array $count = array_fill(0, 10, 0); // Store count of occurrences in count[] for ($i = 0; $i < $n; $i++) $count[ ($arr[$i] / $exp) % 10 ]++; // Change count[i] so that count[i] // now contains actual position of // this digit in output[] for ($i = 1; $i < 10; $i++) $count[$i] += $count[$i - 1]; // Build the output array for ($i = $n - 1; $i>= 0; $i--) { $output[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // Kopieer de uitvoerarray naar arr[], dus // die arr[] bevat nu gesorteerde getallen // volgens het huidige cijfer voor ($i = 0; $i< $n; $i++) $arr[$i] = $output[$i]; } // The main function to that sorts arr[] // of size n using Radix Sort function radixsort(&$arr, $n) { // Find the maximum number to know // number of digits $m = max($arr); // Do counting sort for every digit. Note // that instead of passing digit number, // exp is passed. exp is 10^i where i is // current digit number for ($exp = 1; $m / $exp>0; $exp *= 10) countSort($arr, $n, $exp); } // Een hulpprogrammafunctie om een arrayfunctie PrintArray(&$arr,$n) { for ($i = 0; $i< $n; $i++) echo $arr[$i] . ' '; } // Driver Code $arr = array(170, 45, 75, 90, 802, 24, 2, 66); $n = count($arr); // Function Call radixsort($arr, $n); PrintArray($arr, $n); // This code is contributed by rathbhupendra ?>> Dart // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List array) { int max = array[0]; for (laatste it in array) { if (it> max) { max = it; } } retourmaximum; } /// Een functie om een soort `Lijst` [array] te tellen volgens het /// cijfer dat wordt weergegeven door [exp]. Lijst countSort(Lijst array, int exp) { uiteindelijke lengte = array.length; uiteindelijke uitvoerArr = Lijst.gevuld(lengte, 0); // Een lijst waarbij index het cijfer vertegenwoordigt en waarde het aantal // instances final digitsCount = List.filled(10, 0); // Bewaar het aantal keren dat het voorkomt in cijfersCount[] voor (laatste item in array) {laatste cijfer = item ~/ exp% 10; cijfersCount[cijfer]++; } // Wijzig cijfersCount[i] zodat cijfersCount[i] nu de werkelijke positie bevat // van dit cijfer in outputArr[] voor (int i = 1; i< 10; i++) { digitsCount[i] += digitsCount[i - 1]; } // Build the output array for (int i = length - 1; i>= 0; i--) { laatste item = array[i]; laatste cijfer = item ~/ exp % 10; outputArr[cijfersCount[cijfer] - 1] = item; cijfersTellen[cijfer]--; } return outputArr; } /// De hoofdfunctie die een `List` [array] sorteert met behulp van Radix sorteerlijst radixSort(Lijst array) {// Zoek het maximale aantal om het aantal cijfers te kennen final maxNumber = getMax(array); // Ondiepe kopie van de uiteindelijke invoerarray gesorteerdArr = List.of(array); // Voer een telsortering uit voor elk cijfer. Merk op dat in plaats van het doorgeven van cijfer // nummer, exp wordt doorgegeven. exp is 10^i, waarbij i het huidige cijfer is voor (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortIteration = countSort(sortedArr, exp); gesorteerdArr.clear(); gesorteerdArr.addAll(gesorteerdeIteratie); } retourneert gesorteerdArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; uiteindelijk gesorteerdArray = radixSort(array); print(gesorteerdematrix); } // Deze code is bijgedragen door beeduhboodee>
Uitvoer
2 24 45 66 75 90 170 802>
Complexiteitsanalyse van Radix Sort :
Tijdcomplexiteit:
- Radix sort is een niet-vergelijkend algoritme voor het sorteren van gehele getallen dat gegevens met gehele getallen sorteert door de sleutels te groeperen op basis van de afzonderlijke cijfers die dezelfde significante positie en waarde delen. Het heeft een tijdscomplexiteit van O(d * (n + b)) , waarbij d het aantal cijfers is, n het aantal elementen is en b de basis is van het gebruikte getalsysteem.
- In praktische implementaties is radix sortering vaak sneller dan andere op vergelijkingen gebaseerde sorteeralgoritmen, zoals quicksort of merge sort, voor grote datasets, vooral als de sleutels veel cijfers bevatten. De tijdscomplexiteit groeit echter lineair met het aantal cijfers, en is dus niet zo efficiënt voor kleine datasets.
Hulpruimte:
object tegen json in Java
- Radix-soort heeft ook een ruimtecomplexiteit van O(n + b), waarbij n het aantal elementen is en b de basis van het getalsysteem. Deze ruimtecomplexiteit komt voort uit de noodzaak om buckets te maken voor elke cijferwaarde en om de elementen terug te kopiëren naar de originele array nadat elk cijfer is gesorteerd.
Veelgestelde vragen over RadixSort
Q1. Heeft Radix Sort de voorkeur boven op vergelijkingen gebaseerde sorteeralgoritmen zoals Quick-Sort?
Als we een log hebben2n bits voor elk cijfer lijkt de looptijd van Radix beter te zijn dan Quick Sort voor een breed scala aan invoernummers. De constante factoren die verborgen zijn in de asymptotische notatie zijn hoger voor Radix Sort en Quick-Sort maakt effectiever gebruik van hardwarecaches. Radix sort gebruikt bovendien telsortering als een subroutine en telsortering neemt extra ruimte in beslag om getallen te sorteren.
Vraag 2. Wat als de elementen zich in de variëren van 1 tot n 2 ?
- De ondergrens voor het op vergelijkingen gebaseerde sorteeralgoritme (Merge Sort, Heap Sort, Quick-Sort ... enz.) is Ω(nLogn), d.w.z. ze kunnen het niet beter doen dan nInloggen . Telsortering is een lineair tijdsorteringsalgoritme dat sorteert in O(n+k) tijd wanneer elementen zich in het bereik van 1 tot k bevinden.
- We kunnen telsortering niet gebruiken omdat voor telsortering O(n nodig is2) wat slechter is dan op vergelijkingen gebaseerde sorteeralgoritmen. Kunnen we zo'n array in lineaire tijd sorteren?
- Sorteer Radix is het antwoord. Het idee van Radix Sort is om cijfer voor cijfer te sorteren, beginnend van het minst significante cijfer tot het meest significante cijfer. Radix sort gebruikt telsortering als subroutine om te sorteren.