Razvrsti Radix je algoritem linearnega razvrščanja, ki razvršča elemente tako, da jih obdela števko za števko. Je učinkovit algoritem za razvrščanje celih števil ali nizov s ključi fiksne velikosti.
Namesto neposredne primerjave elementov Radix Sort razdeli elemente v vedra na podlagi vrednosti vsake števke. Z večkratnim razvrščanjem elementov po njihovih pomembnih številkah, od najmanj pomembnih do najpomembnejših, Radix Sort doseže končni razvrščeni vrstni red.
Algoritem razvrščanja Radix
Ključna ideja Radix Sort je izkoriščanje koncepta mestne vrednosti. Predvideva, da bo razvrščanje števil števko za števko na koncu povzročilo popolnoma razvrščen seznam. Razvrščanje po korenu je mogoče izvesti z različnimi različicami, kot sta razvrščanje po korenu z najmanj pomembno cifro (LSD) ali razvrščanje po korenu z najpomembnejšo števko (MSD).
Kako deluje algoritem razvrščanja Radix?
Za izvedbo razvrščanja po radiksu v matriki [170, 45, 75, 90, 802, 24, 2, 66] sledimo tem korakom:
Kako deluje algoritem razvrščanja Radix | Korak 1
Korak 1: Poiščite največji element v nizu, ki je 802. Ima tri števke, zato bomo ponovili trikrat, enkrat za vsako pomembno mesto.
2. korak: Razvrsti elemente glede na števke mest enote (X=0). Za razvrščanje števk na vsakem pomembnem mestu uporabljamo stabilno tehniko razvrščanja, kot je razvrščanje s štetjem.
kako onemogočiti razvijalski načinRazvrščanje glede na mesto enote:
- Izvedite razvrščanje s štetjem na matriki na podlagi števk mest enote.
- Razvrščeno polje na podlagi mesta enote je [170, 90, 802, 2, 24, 45, 75, 66].
Kako deluje algoritem razvrščanja Radix | 2. korak
3. korak: Razvrsti elemente na podlagi desetic.
Razvrščanje glede na mesto desetic:
- Izvedite razvrščanje s štetjem na matriki na podlagi desetic.
- Razvrščen niz na podlagi mesta desetic je [802, 2, 24, 45, 66, 170, 75, 90].
Kako deluje algoritem razvrščanja Radix | 3. korak
4. korak: Elemente razvrsti glede na stotice.
Razvrščanje glede na mesto stotin:
- Izvedite razvrščanje s štetjem v matriki na podlagi števk stotin.
- Razvrščena matrika na podlagi mesta stotic je [2, 24, 45, 66, 75, 90, 170, 802].
Kako deluje algoritem razvrščanja Radix | 4. korak
5. korak: Matrika je zdaj razvrščena v naraščajočem vrstnem redu.
c logičnoKončno razvrščeno polje z razvrščanjem po osnovi je [2, 24, 45, 66, 75, 90, 170, 802].
primer seznama v JaviKako deluje algoritem razvrščanja Radix | 5. korak
Spodaj je izvedba za zgornje ilustracije:
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]; vrnitev mx; } // Funkcija za štetje vrste arr[] // glede na števko, // ki jo predstavlja exp. void countSort(int arr[], int n, int exp) { // Izhodna matrika int output[n]; int i, count[10] = { 0 }; // Shrani število pojavitev // v count[] za (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]; štetje [(arr[i] / exp) % 10]--; } // Kopiraj izhodno matriko v arr[], // tako da arr[] zdaj vsebuje razvrščena // števila glede na trenutno števko za (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); } // Pomožna funkcija za tiskanje matrike 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]; vrnitev mx; } // Funkcija za štetje vrste arr[] glede na // števko, ki jo predstavlja exp. static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // izhodna matrika int i; int count[] = novo int[10]; Arrays.fill(štetje, 0); // Shrani število pojavitev v count[] za (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]; štetje [(arr[i] / exp) % 10]--; } // Kopiraj izhodno matriko v arr[], tako da arr[] zdaj // vsebuje razvrščena števila glede na trenutno // števko za (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); } // Pomožna funkcija za tiskanje matrike 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: indeks = arr[i] // exp1 output[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # Kopiranje izhodne matrike v arr[] , # tako da arr zdaj vsebuje razvrščena števila i = 0 za i v range(0, len(arr)): arr[i] = output[i] # Metoda, ki jo je treba narediti Radix Sort def radixSort(arr): # Poišči največ število za poznavanje števila števk max1 = max(arr) # Izvedite razvrščanje s štetjem za vsako števko. Upoštevajte, da je namesto številke # podana exp. exp je 10^i # kjer je i trenutna številka števke exp = 1 medtem ko je max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Koda gonilnika arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Klic funkcije radixSort(arr) za i in range(len(arr)): print(arr[i], end=' ') # To kodo je prispeval Mohit Kumra # Uredil 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]; vrnitev mx; } // Funkcija za štetje vrste arr[] glede na // števko, ki jo predstavlja exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // izhodna matrika int i; int[] count = novo int[10]; // inicializacija vseh elementov štetja na 0 za (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[count[(arr[i] / exp) % 10] - 1] = arr[i]; štetje [(arr[i] / exp) % 10]--; } // Kopiraj izhodno matriko v arr[], tako da arr[] zdaj // vsebuje razvrščena števila glede na trenutno // števko za (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); } // Pomožna funkcija za tiskanje matrike 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]; } return mx; } // Funkcija za štetje vrste arr[] glede na // števko, ki jo predstavlja exp. funkcija countSort(arr, exp) { const length = arr.length; naj izhod = Array(length); // izhodna matrika let count = Array(10).fill(0, 0); // Shrani število pojavitev v count[] for (naj 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; izhod[štetje[številka] - 1] = arr[i]; štetje [števka]--; } vrni izhod; } // Glavna funkcija za razvrščanje arr[] z uporabo Radix Sort function radixSort(arr) { // Poišči največje število, ki ga poznaš število števk const maxNumber = getMax(arr); // Ustvari plitvo kopijo, kjer bodo shranjene razvrščene vrednosti let sortedArr = [...arr]; // Izvedite razvrščanje s štetjem za vsako števko. Upoštevajte, da se // namesto posredovanja številke številke posreduje exp. // exp je 10^i, kjer je i trenutna številka števke za (naj bo exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Pridobi iteracijo sortiranja števila const sortedIteration = countSort(sortedArr , exp); sortedArr = sortedIteration; } vrni sortedArr; } /*Koda gonilnika*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Klic funkcije const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // To kodo je prispeval 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 ]--; } // Kopiraj izhodno matriko v arr[], tako // da arr[] zdaj vsebuje razvrščena števila // glede na trenutno števko za ($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); } // Pomožna funkcija za tiskanje matrične funkcije 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 ?>> Pikado // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List polje) { int max = polje[0]; for (končno v matriki) { if (it> max) { max = it; } } vrni max; } /// Funkcija za razvrščanje `List` [matrika] glede na /// števko, ki jo predstavlja [exp]. Seznam countSort(Seznam array, int exp) { končna dolžina = array.length; končni izhodArr = List.filled(dolžina, 0); // Seznam, kjer indeks predstavlja števko, vrednost pa število // pojavitev final digitsCount = List.filled(10, 0); // Shrani število pojavitev v digitsCount[] for (končna postavka v matriki) { končna cifra = postavka ~/ exp % 10; digitsCount[številka]++; } // Spremeni digitsCount[i] tako, da digitsCount[i] zdaj vsebuje dejanski položaj // te števke v 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--) { končna postavka = niz[i]; končna številka = item ~/ exp % 10; outputArr[digitsCount[digit] - 1] = element; številkeŠtetje[številka]--; } vrni outputArr; } /// Glavna funkcija za razvrščanje `List` [matrike] z uporabo Radix sort List radixSort(Seznam array) { // Poiščite največje število, da poznate število števk final maxNumber = getMax(array); // Plitka kopija vhodne matrike final sortedArr = List.of(array); // Izvedite razvrščanje s štetjem za vsako števko. Upoštevajte, da se namesto podajanja številke // številke posreduje exp. exp je 10^i, kjer je i trenutna številka števke za (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); sortedArr.clear(); sortedArr.addAll(sortedIteration); } vrni sortedArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; final sortedArray = radixSort(matrika); natisni (sortedArray); } // To kodo je prispeval beeduhboodee>
Izhod
2 24 45 66 75 90 170 802>
Analiza kompleksnosti Radix Sort :
Časovna zapletenost:
- Razvrščanje po radixu je neprimerljiv algoritem za razvrščanje celih števil, ki razvršča podatke s ključi celih števil z združevanjem ključev po posameznih števkah, ki imajo enak pomemben položaj in vrednost. Ima časovno zapletenost O(d * (n + b)) , kjer je d število števk, n število elementov in b osnova uporabljenega številskega sistema.
- V praktičnih izvedbah je razvrščanje po osnovi pogosto hitrejše od drugih algoritmov za razvrščanje, ki temeljijo na primerjavi, kot sta hitro razvrščanje ali razvrščanje z združevanjem, za velike nabore podatkov, še posebej, če imajo ključi veliko števk. Vendar pa njegova časovna kompleksnost raste linearno s številom števk, zato ni tako učinkovita za majhne nize podatkov.
Pomožni prostor:
- Razvrstitev Radix ima tudi prostorsko kompleksnost O(n + b), kjer je n število elementov in b osnova številskega sistema. Ta zapletenost prostora izhaja iz potrebe po ustvarjanju veder za vsako števčno vrednost in kopiranju elementov nazaj v izvirno matriko, potem ko je vsaka števka razvrščena.
Pogosto zastavljena vprašanja o RadixSortu
Q1. Ali je Radix Sort boljša od algoritmov za razvrščanje, ki temeljijo na primerjavi, kot je Quick-Sort?
Če imamo dnevnik2n bitov za vsako števko, se zdi, da je čas delovanja Radixa boljši od hitrega razvrščanja za širok razpon vhodnih števil. Konstantni faktorji, skriti v asimptotičnem zapisu, so višji za Radix Sort in Quick-Sort učinkoviteje uporablja predpomnilnike strojne opreme. Poleg tega razvrščanje Radix uporablja razvrščanje s štetjem kot podprogram in razvrščanje s štetjem zavzame dodaten prostor za razvrščanje števil.
Q2. Kaj pa, če so elementi v razpon od 1 do n 2 ?
- Spodnja meja za algoritem razvrščanja na podlagi primerjave (razvrščanje z združitvijo, razvrščanje kopice, hitro razvrščanje itd.) je Ω(nLogn), kar pomeni, da ne morejo delati bolje kot nPrijava . Razvrščanje s štetjem je algoritem linearnega časovnega razvrščanja, ki razvršča v O(n+k) času, ko so elementi v območju od 1 do k.
- Ne moremo uporabiti razvrščanja s štetjem, ker bo razvrščanje s štetjem trajalo O(n2), kar je slabše od algoritmov za razvrščanje, ki temeljijo na primerjavi. Ali lahko razvrstimo tako matriko v linearnem času?
- Razvrsti Radix je odgovor. Ideja Radix Sort je razvrščanje števk za števkami, začenši od najmanj pomembne števke do najbolj pomembne števke. Radix sort uporablja razvrščanje s štetjem kot podprogram za razvrščanje.