Sortera Radix är en linjär sorteringsalgoritm som sorterar element genom att bearbeta dem siffra för siffra. Det är en effektiv sorteringsalgoritm för heltal eller strängar med nycklar med fast storlek.
Istället för att jämföra element direkt, distribuerar Radix Sort elementen i hinkar baserat på varje siffras värde. Genom att upprepade gånger sortera elementen efter deras signifikanta siffror, från den minst signifikanta till den mest signifikanta, uppnår Radix Sort den slutliga sorterade ordningen.
Radix sorteringsalgoritm
Nyckeltanken bakom Radix Sort är att utnyttja begreppet platsvärde. Det förutsätter att sortering av nummer siffra för siffra så småningom kommer att resultera i en fullständigt sorterad lista. Radixsortering kan utföras med olika varianter, såsom minst signifikanta siffror (LSD) Radixsortering eller mest signifikanta siffror (MSD) Radixsortering.
Hur fungerar Radix Sort Algorithm?
För att utföra radixsortering på arrayen [170, 45, 75, 90, 802, 24, 2, 66], följer vi dessa steg:
Hur fungerar Radix Sort Algorithm | Steg 1
Steg 1: Hitta det största elementet i arrayen, vilket är 802. Det har tre siffror, så vi upprepar tre gånger, en gång för varje betydande plats.
Steg 2: Sortera elementen baserat på enhetsplatssiffrorna (X=0). Vi använder en stabil sorteringsteknik, som att räkna sortering, för att sortera siffrorna på varje betydande plats.
shreya ghoshals första makeSortering baserat på enhetsplats:
- Utför räknesortering på matrisen baserat på enhetsplatssiffrorna.
- Den sorterade matrisen baserat på enhetsplatsen är [170, 90, 802, 2, 24, 45, 75, 66].
Hur fungerar Radix Sort Algorithm | Steg 2
Steg 3: Sortera elementen baserat på tiotalssiffrorna.
Sortering baserat på tiotalsplatsen:
- Utför räknesortering på matrisen baserat på tiotalssiffrorna.
- Den sorterade matrisen baserad på tiotalsplatsen är [802, 2, 24, 45, 66, 170, 75, 90].
Hur fungerar Radix Sort Algorithm | Steg 3
Steg 4: Sortera elementen baserat på hundratals platssiffror.
Sortering baserat på hundratals plats:
- Utför räknesortering på matrisen baserat på hundratals platssiffror.
- Den sorterade matrisen baserat på hundratalsplatsen är [2, 24, 45, 66, 75, 90, 170, 802].
Hur fungerar Radix Sort Algorithm | Steg 4
Steg 5: Arrayen är nu sorterad i stigande ordning.
sträng till heltal i javaDen slutliga sorterade matrisen som använder radixsortering är [2, 24, 45, 66, 75, 90, 170, 802].
linux felkoderHur fungerar Radix Sort Algorithm | Steg 5
Nedan är implementeringen för ovanstående illustrationer:
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]; returnera mx; } // En funktion för att räkna sorts arr[] // enligt siffran // representerad av exp. void countSort(int arr[], int n, int exp) { // Output array int output[n]; int i, count[10] = { 0 }; // Lagra antalet förekomster // i antal[] för (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[antal[(arr[i] / exp) % 10] - 1] = arr[i]; räkna [(arr[i] / exp) % 10]--; } // Kopiera utmatrisen till arr[], // så att arr[] nu innehåller sorterade //-nummer enligt aktuell siffra för (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); } // En verktygsfunktion för att skriva ut en 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]; returnera mx; } // En funktion för att räkna sorts arr[] enligt // siffran som representeras av exp. static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // output array int i; int count[] = new int[10]; Arrays.fill(count, 0); // Lagra antalet förekomster i antal[] för (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[antal[(arr[i] / exp) % 10] - 1] = arr[i]; räkna [(arr[i] / exp) % 10]--; } // Kopiera utmatrisen till arr[], så att arr[] nu // innehåller sorterade tal enligt aktuell // siffra för (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); } // En verktygsfunktion för att skriva ut en array statisk 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 # Kopierar utdatamatrisen till arr[] , # så att arr nu innehåller sorterade tal i = 0 för i inom range(0, len(arr)): arr[i] = output[i] # Metod att göra Radix Sortera def radixSort(arr): # Hitta det maximala antal att veta antal siffror max1 = max(arr) # Gör räknesortering för varje siffra. Observera att i stället för # för passerande siffra passerar exp. exp är 10^i # där i är nuvarande siffra exp = 1 medan max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Förarkod arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funktion Anrop radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # Denna kod har bidragit med Mohit Kumra # Redigerad av 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]; returnera mx; } // En funktion för att räkna sorts arr[] enligt // siffran som representeras av exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // output array int i; int[] count = new int[10]; // initierar alla element i räkningen till 0 för (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; i--) { output[antal[(arr[i] / exp) % 10] - 1] = arr[i]; räkna [(arr[i] / exp) % 10]--; } // Kopiera utmatrisen till arr[], så att arr[] nu // innehåller sorterade tal enligt aktuell // siffra för (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); } // En verktygsfunktion för att skriva ut en array public static void print(int[] arr, int n) { for (int i = 0; i< 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]; } returnera mx; } // En funktion för att räkna sorts arr[] enligt // siffran som representeras av exp. function countSort(arr, exp) { const length = arr.length; let output = Array(längd); // output array let count = Array(10).fill(0, 0); // Lagra antalet förekomster i antal[] för (låt 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 digit = Math.floor(arr[i] / exp) % 10; output[antal[siffra] - 1] = arr[i]; räkna[siffra]--; } returnera utgång; } // Huvudfunktionen som sorterar arr[] med Radix Sorteringsfunktion radixSort(arr) { // Hitta det maximala antalet för att veta antalet siffror const maxNumber = getMax(arr); // Skapa en ytlig kopia där de sorterade värdena kommer att behållas let sortedArr = [...arr]; // Gör räknesortering för varje siffra. Observera att // istället för att passera siffror, exp passeras. // exp är 10^i där i är aktuellt siffror för (låt exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Få Count sort iteration const sortedIteration = countSort(sortedArr) , exp); sortedArr = sortedIteration; } return sortedArr; } /*Förarkod*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funktion Anrop const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Denna kod är bidragit av 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 ]--; } // Kopiera utmatrisen till arr[], så // att arr[] nu innehåller sorterade tal // enligt aktuell siffra för ($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); } // En verktygsfunktion för att skriva ut en arrayfunktion 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 ?>> Pil // 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 (final it in array) { if (it> max) { max = it; } } return max; } /// En funktion för att göra en räkning av typen 'List' [array] enligt ///-siffran som representeras av [exp]. Lista countSort(List array, int exp) { final length = array.length; final outputArr = List.filled(length, 0); // En lista där index representerar siffran och värdet representerar antalet // förekomster final digitsCount = List.filled(10, 0); // Lagra antalet förekomster i siffrorCount[] för (slutlig artikel i array) { final digit = item ~/ exp % 10; siffrorCount[siffra]++; } // Ändra siffrorCount[i] så att digitsCount[i] nu innehåller den faktiska positionen // för denna siffra i outputArr[] för (int i = 1; i< 10; i++) { digitsCount[i] += digitsCount[i - 1]; } // Build the output array for (int i = length - 1; i>= 0; i--) { final item = array[i]; slutsiffra = objekt ~/ exp % 10; outputArr[digitsCount[siffra] - 1] = artikel; siffrorCount[siffra]--; } returnera outputArr; } /// Huvudfunktionen som sorterar en `List` [array] med Radix sorteringslista radixSort(lista array) { // Hitta det maximala antalet för att veta antalet siffror final maxNumber = getMax(array); // Grund kopia av indatamatrisen final sortedArr = List.of(array); // Gör räknesortering för varje siffra. Observera att istället för att passera siffran // nummer, skickas exp. exp är 10^i, där i är aktuellt siffror för (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); sortedArr.clear(); sortedArr.addAll(sortedIteration); } return sortedArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; final sortedArray = radixSort(array); print(sortedArray); } // Denna kod är bidragit av beeduhboodee>
Produktion
2 24 45 66 75 90 170 802>
Komplexitetsanalys av Radix Sort :
Tidskomplexitet:
- Radix sort är en icke-jämförande heltalssorteringsalgoritm som sorterar data med heltalsnycklar genom att gruppera nycklarna efter de individuella siffrorna som delar samma signifikanta position och värde. Det har en tidskomplexitet av O(d * (n + b)) , där d är antalet siffror, n är antalet element och b är basen för det talsystem som används.
- I praktiska implementeringar är radixsortering ofta snabbare än andra jämförelsebaserade sorteringsalgoritmer, såsom quicksort eller merge sort, för stora datamängder, speciellt när nycklarna har många siffror. Dess tidskomplexitet växer dock linjärt med antalet siffror, och därför är den inte lika effektiv för små datamängder.
Hjälputrymme:
- Radix sort har också en rymdkomplexitet av O(n + b), där n är antalet element och b är basen i talsystemet. Denna rymdkomplexitet kommer från behovet av att skapa hinkar för varje siffervärde och att kopiera elementen tillbaka till den ursprungliga arrayen efter att varje siffra har sorterats.
Vanliga frågor om RadixSort
Q1. Är Radix Sort att föredra framför jämförelsebaserade sorteringsalgoritmer som Quick-Sort?
Om vi har logg2n bitar för varje siffra verkar körtiden för Radix vara bättre än snabbsortering för ett brett spektrum av inmatade nummer. De konstanta faktorerna dolda i asymptotisk notation är högre för Radix Sort och Quick-Sort använder hårdvarucacher mer effektivt. Radix sortering använder också räknesortering som en subrutin och räknesortering tar extra utrymme för att sortera siffror.
Q2. Tänk om elementen finns i sträcker sig från 1 till n 2 ?
- Den nedre gränsen för den jämförelsebaserade sorteringsalgoritmen (Merge Sort, Heap Sort, Quick-Sort .. etc) är Ω(nLogn), d.v.s. de kan inte göra bättre än nLogn . Räknesortering är en linjär tidssorteringsalgoritm som sorterar i O(n+k)-tid när element är i intervallet från 1 till k.
- Vi kan inte använda räknesortering eftersom räknesortering tar O(n2) vilket är sämre än jämförelsebaserade sorteringsalgoritmer. Kan vi sortera en sådan array i linjär tid?
- Sortera Radix är svaret. Idén med Radix Sort är att sortera siffra för siffra från den minst signifikanta siffran till den mest signifikanta siffran. Radix sortering använder räknesortering som en subrutin för att sortera.