Sortér Radix er en lineær sorteringsalgoritme, der sorterer elementer ved at behandle dem ciffer for ciffer. Det er en effektiv sorteringsalgoritme for heltal eller strenge med nøgler med fast størrelse.
I stedet for at sammenligne elementer direkte, fordeler Radix Sort elementerne i buckets baseret på hvert ciffers værdi. Ved gentagne gange at sortere elementerne efter deres signifikante cifre, fra den mindst signifikante til den mest signifikante, opnår Radix Sort den endelige sorterede rækkefølge.
Radix sorteringsalgoritme
Nøgleideen bag Radix Sort er at udnytte begrebet stedværdi. Det forudsætter, at sortering af tal ciffer for ciffer i sidste ende vil resultere i en fuldt sorteret liste. Radix Sort kan udføres ved hjælp af forskellige variationer, såsom Least Significant Digit (LSD) Radix Sort eller Most Significant Digit (MSD) Radix Sort.
Hvordan fungerer Radix Sort Algorithm?
For at udføre radix-sortering på arrayet [170, 45, 75, 90, 802, 24, 2, 66], følger vi disse trin:
Hvordan fungerer Radix Sort Algorithm | Trin 1
Trin 1: Find det største element i arrayet, som er 802. Det har tre cifre, så vi vil iterere tre gange, én gang for hvert signifikant sted.
Trin 2: Sorter elementerne ud fra enhedspladscifrene (X=0). Vi bruger en stabil sorteringsteknik, såsom at tælle sortering, til at sortere cifrene på hvert væsentligt sted.
mvc i fjederrammeSortering baseret på enhedssted:
- Udfør tællesortering på arrayet baseret på enhedspladscifrene.
- Det sorterede array baseret på enhedspladsen er [170, 90, 802, 2, 24, 45, 75, 66].
Hvordan virker Radix Sort Algorithm | Trin 2
Trin 3: Sorter elementerne ud fra ti-pladscifrene.
Sortering baseret på tierpladsen:
- Udfør tællesortering på arrayet baseret på ti-pladscifrene.
- Det sorterede array baseret på tierpladsen er [802, 2, 24, 45, 66, 170, 75, 90].
Hvordan virker Radix Sort Algorithm | Trin 3
Trin 4: Sorter elementerne ud fra de hundrede steds cifre.
Sortering baseret på hundredvis sted:
- Udfør tællesortering på arrayet baseret på hundredvis af stedcifre.
- Det sorterede array baseret på hundredepladsen er [2, 24, 45, 66, 75, 90, 170, 802].
Hvordan virker Radix Sort Algorithm | Trin 4
Trin 5: Arrayet er nu sorteret i stigende rækkefølge.
android.process.acore bliver ved med at stoppeDet endelige sorterede array ved hjælp af radix-sortering er [2, 24, 45, 66, 75, 90, 170, 802].
Hvordan virker Radix Sort Algorithm | Trin 5
Nedenfor er implementeringen af ovenstå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]; returnere mx; } // En funktion til at tælle slags arr[] // ifølge cifferet // repræsenteret ved exp. void countSort(int arr[], int n, int exp) { // Output array int output[n]; int i, tælle[10] = { 0 }; // Gem tælling af forekomster // i 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]; tælle[(arr[i] / exp) % 10]--; } // Kopier output-arrayet til arr[], //, så arr[] nu indeholder sorterede //-tal i henhold til det aktuelle ciffer for (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 hjælpefunktion til at udskrive et 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]; returnere mx; } // En funktion til at tælle slags arr[] i henhold til // cifferet repræsenteret af exp. statisk 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); // Gem tælling af forekomster i 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]; tælle[(arr[i] / exp) % 10]--; } // Kopier output-arrayet til arr[], så arr[] nu // indeholder sorterede tal i henhold til nuværende // ciffer for (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 hjælpefunktion til at udskrive et 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 # Kopierer output-arrayet til arr[] , # så arr nu indeholder sorterede tal i = 0 for i i interval(0, len(arr)): arr[i] = output[i] # Metode til at gøre Radix Sort def radixSort(arr): # Find maksimum antal at kende antal cifre max1 = max(arr) # Lav tællesort for hvert ciffer. Bemærk, at i stedet for # for bestået ciffer nummer, er exp bestået. exp er 10^i # hvor i er det aktuelle ciffernummer exp = 1 mens max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Driverkode arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funktion Kald radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # Denne kode er bidraget af Mohit Kumra # Redigeret af 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]; returnere mx; } // En funktion til at tælle slags arr[] i henhold til // cifferet repræsenteret af 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]; // initialisering af alle elementer af tælle til 0 for (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]; tælle[(arr[i] / exp) % 10]--; } // Kopier output-arrayet til arr[], så arr[] nu // indeholder sorterede tal i henhold til nuværende // ciffer for (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 hjælpefunktion til at udskrive et 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]; } returner mx; } // En funktion til at tælle slags arr[] i henhold til // cifferet repræsenteret af exp. function countSort(arr, exp) { const length = arr.length; lad output = Array(længde); // output array let count = Array(10).fill(0, 0); // Gem antallet af forekomster i antal[] for (lad 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[ciffer] - 1] = arr[i]; tælle[ciffer]--; } returnere output; } // Hovedfunktionen til at sortere arr[] ved hjælp af Radix Sort funktion radixSort(arr) { // Find det maksimale antal for at kende antallet af cifre const maxNumber = getMax(arr); // Opret en lavvandet kopi, hvor de sorterede værdier vil blive holdt let sortedArr = [...arr]; // Gør tællesort for hvert ciffer. Bemærk, at // i stedet for at bestå ciffernummer, er exp bestået. // exp er 10^i hvor i er det aktuelle ciffertal for (lad exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Hent Count sort iteration const sortedIteration = countSort(sortedArr) , exp); sortedArr = sortedIteration; } returner sorteretArr; } /*Kørekode*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funktion Kald const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Denne kode er bidraget af 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 ]--; } // Kopier output-arrayet til arr[], så // at arr[] nu indeholder sorterede tal // i henhold til det aktuelle ciffer for ($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 hjælpefunktion til at udskrive en matrixfunktion 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 matrix) { int max = matrix[0]; for (final it in array) { if (it> max) { max = it; } } return max; } /// En funktion til at tælle slags 'List' [array] i henhold til /// cifferet repræsenteret af [exp]. Liste tælSorter(Liste matrix, int exp) { endelig længde = matrix.længde; final outputArr = List.filled(længde, 0); // En liste hvor indeks repræsenterer cifferet og værdi repræsenterer antallet af // forekomster final digitsCount = List.filled(10, 0); // Gem antallet af forekomster i digitsCount[] for (endelig vare i array) { final digit = item ~/ exp % 10; digitsCount[digit]++; } // Skift digitsCount[i], så digitsCount[i] nu indeholder den faktiske position // af dette ciffer i outputArr[] for (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 = matrix[i]; sidste ciffer = vare ~/ exp % 10; outputArr[digitsCount[digit] - 1] = vare; digitsCount[digit]--; } returner outputArr; } /// Hovedfunktionen til at sortere en `List` [array] ved hjælp af Radix sort List radixSort(Liste array) { // Find det maksimale antal for at kende antal cifre final maxNumber = getMax(array); // Overfladisk kopi af input-arrayet final sortedArr = List.of(array); // Gør tællesort for hvert ciffer. Bemærk, at i stedet for at bestå ciffer // nummer, er exp bestået. exp er 10^i, hvor i er det aktuelle ciffertal for (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); sortedArr.clear(); sortedArr.addAll(sortedIteration); } returner sorteretArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; final sortedArray = radixSort(array); print(sorteretArray); } // Denne kode er bidraget af beeduhboodee>
Produktion
2 24 45 66 75 90 170 802>
Kompleksitetsanalyse af Radix Sort :
Tidskompleksitet:
- Radix sort er en ikke-komparativ heltalssorteringsalgoritme, der sorterer data med heltalsnøgler ved at gruppere nøglerne efter de individuelle cifre, som deler den samme betydningsfulde position og værdi. Det har en tidskompleksitet på O(d * (n + b)) , hvor d er antallet af cifre, n er antallet af elementer, og b er bunden af det talsystem, der anvendes.
- I praktiske implementeringer er radix-sortering ofte hurtigere end andre sammenligningsbaserede sorteringsalgoritmer, såsom quicksort eller merge sort, for store datasæt, især når nøglerne har mange cifre. Dens tidskompleksitet vokser dog lineært med antallet af cifre, og det er derfor ikke så effektivt for små datasæt.
Hjælpeplads:
binært træ java
- Radix sort har også en rumkompleksitet på O(n + b), hvor n er antallet af elementer og b er grunden af talsystemet. Denne pladskompleksitet kommer fra behovet for at oprette buckets for hver cifferværdi og at kopiere elementerne tilbage til det originale array, efter at hvert ciffer er blevet sorteret.
Ofte stillede spørgsmål om RadixSort
Q1. Er Radix Sort at foretrække frem for sammenligningsbaserede sorteringsalgoritmer som Quick-Sort?
Hvis vi har log2n bit for hvert ciffer, lader Radix's køretid at være bedre end Quick Sort for en lang række inputtal. De konstante faktorer, der er skjult i asymptotisk notation, er højere for Radix Sort, og Quick-Sort bruger hardware-caches mere effektivt. Radix sort bruger også tællesortering som en underrutine, og tællesortering tager ekstra plads til at sortere tal.
Q2. Hvad hvis elementerne er i spænder fra 1 til n 2 ?
- Den nedre grænse for den sammenligningsbaserede sorteringsalgoritme (Merge Sort, Heap Sort, Quick-Sort .. etc) er Ω(nLogn), dvs. de kan ikke gøre det bedre end nLogin . Tællesortering er en lineær tidssorteringsalgoritme, der sorterer i O(n+k) tid, når elementer er i området fra 1 til k.
- Vi kan ikke bruge tællesortering, fordi tællesortering tager O(n2), hvilket er værre end sammenligningsbaserede sorteringsalgoritmer. Kan vi sortere et sådant array i lineær tid?
- Sortér Radix er svaret. Ideen med Radix Sort er at lave ciffer-for-ciffer sortering fra det mindst betydende ciffer til det mest betydende ciffer. Radix sort bruger tællesortering som en underrutine til at sortere.