Zoradiť Radix je lineárny triediaci algoritmus, ktorý triedi prvky tak, že ich spracováva číslicu po číslici. Je to efektívny triediaci algoritmus pre celé čísla alebo reťazce s kľúčmi s pevnou veľkosťou.
Namiesto priameho porovnávania prvkov rozdeľuje Radix Sort prvky do segmentov na základe hodnoty každej číslice. Opakovaným triedením prvkov podľa platných číslic, od najmenej významných po najvýznamnejšie, Radix Sort dosiahne konečné zoradené poradie.
Radixov algoritmus triedenia
Kľúčovou myšlienkou Radix Sort je využiť koncept hodnoty miesta. Predpokladá, že triedenie čísel číslicu po číslici nakoniec povedie k úplne zoradenému zoznamu. Radixové triedenie je možné vykonávať pomocou rôznych variácií, ako je triedenie podľa najmenej významnej číslice (LSD) alebo triedenie s najvýznamnejšou číslicou (MSD).
Ako funguje Radix Sort Algorithm?
Ak chcete vykonať radixové triedenie v poli [170, 45, 75, 90, 802, 24, 2, 66], postupujte takto:
Ako funguje Radix Sort Algorithm | Krok 1
Krok 1: Nájdite najväčší prvok v poli, čo je 802. Má tri číslice, takže budeme opakovať trikrát, raz pre každé významné miesto.
Krok 2: Zoraďte prvky na základe číslic jednotky (X=0). Na triedenie číslic na každom významnom mieste používame stabilnú techniku triedenia, ako je počítacie triedenie.
nudné nulyTriedenie podľa miesta jednotky:
- Vykonajte triedenie počítania na poli na základe číslic jednotky.
- Zoradené pole na základe jednotky je [170, 90, 802, 2, 24, 45, 75, 66].
Ako funguje Radix Sort Algorithm | Krok 2
Krok 3: Zoraďte prvky podľa desatinných miest.
Triedenie podľa miesta v desiatkach:
- Uskutočnite triedenie počítania v poli na základe desatinných miest.
- Zoradené pole na základe desiatky je [802, 2, 24, 45, 66, 170, 75, 90].
Ako funguje Radix Sort Algorithm | Krok 3
Krok 4: Zoraďte prvky na základe stoviek číslic.
Triedenie podľa stoviek miest:
- Vykonajte triedenie počítania v poli na základe stoviek číslic.
- Zoradené pole na základe stoviek je [2, 24, 45, 66, 75, 90, 170, 802].
Ako funguje Radix Sort Algorithm | Krok 4
Krok 5: Pole je teraz zoradené vo vzostupnom poradí.
nahradiť reťazec javaKonečné triedené pole pomocou radixového triedenia je [2, 24, 45, 66, 75, 90, 170, 802].
Ako funguje Radix Sort Algorithm | Krok 5
Nižšie je uvedená implementácia pre vyššie uvedené ilustrácie:
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]; návrat mx; } // Funkcia na počítanie typu arr[] // podľa číslice // reprezentovanej exp. void countSort(int arr[], int n, int exp) { // Výstupné pole int output[n]; int i, počet[10] = { 0 }; // Uloženie počtu výskytov // do počtu[] pre (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[počet[(arr[i] / exp) % 10] - 1] = arr[i]; počet[(arr[i] / exp) % 10]--; } // Skopírujte výstupné pole do arr[], // tak, aby arr[] teraz obsahovalo zoradené // čísla podľa aktuálnej číslice pre (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) pocetSort(arr, n, exp); } // Pomocná funkcia na tlač poľa 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]; návrat mx; } // Funkcia na počítanie typu arr[] podľa // číslice reprezentovanej exp. static void pocetSort(int arr[], int n, int exp) { int vystup[] = new int[n]; // výstup poľa int i; int pocet[] = new int[10]; Arrays.fill(count, 0); // Uloženie počtu výskytov do count[] pre (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[počet[(arr[i] / exp) % 10] - 1] = arr[i]; počet[(arr[i] / exp) % 10]--; } // Skopírujte výstupné pole do arr[], takže arr[] teraz // obsahuje čísla zoradené podľa aktuálnej // číslice pre (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) pocetSort(arr, n, exp); } // Pomocná funkcia na tlač statického poľa 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 # Kopírovanie výstupného poľa do arr[] , # takže arr teraz obsahuje zoradené čísla i = 0 pre i v rozsahu (0, len(arr)): arr[i] = výstup[i] # Spôsob vykonania Radix Sort def radixSort(arr): # Nájdite maximum číslo, ktoré treba poznať počet číslic max1 = max(arr) # Urobte triedenie počítania pre každú číslicu. Všimnite si, že namiesto # prechádzajúceho ciferného čísla sa odovzdáva exp. exp je 10^i # kde i je aktuálne číslo exp = 1, zatiaľ čo max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Kód ovládača arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funkcia Volanie radixSort(arr) pre i v rozsahu(len(arr)): print(arr[i], end=' ') # Tento kód prispel Mohit Kumra # Upravil 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]; návrat mx; } // Funkcia na počítanie typu arr[] podľa // číslice reprezentovanej exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // výstup poľa int i; int[] pocet = new int[10]; // inicializácia všetkých prvkov počítania na 0 pre (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[počet[(arr[i] / exp) % 10] - 1] = arr[i]; počet[(arr[i] / exp) % 10]--; } // Skopírujte výstupné pole do arr[], takže arr[] teraz // obsahuje čísla zoradené podľa aktuálnej // číslice pre (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) pocetSort(arr, n, exp); } // Pomocná funkcia na tlač poľa 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; } // Funkcia na počítanie typu arr[] podľa // číslice reprezentovanej exp. function countSort(arr, exp) { const length = arr.length; nech vystup = Array(dlzka); // výstup poľa nech count = Array(10).fill(0, 0); // Uloží počet výskytov do count[] for (nech 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; výstup[počet[číslica] - 1] = arr[i]; počet[číslica]--; } návratový výstup; } // Hlavná funkcia, ktorá triedi arr[] pomocou funkcie Radix Sort radixSort(arr) { // Nájdite maximálny počet, aby ste poznali počet číslic const maxNumber = getMax(arr); // Vytvorte plytkú kópiu, v ktorej budú uložené zoradené hodnoty let sortArr = [...arr]; // Vykonajte triedenie počítania pre každú číslicu. Všimnite si, že // namiesto číselného čísla sa odovzdáva exp. // exp je 10^i kde i je aktuálne ciferné číslo pre (nech exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Získanie iterácie zoradenia Const sortIteration = countSort(sortedArr , exp); sortArr = sortedIteration; } return sortedArr; } /*Kód ovládača*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Volanie funkcie const sortArr = radixSort(arr); console.log(sortedArr.join(' ')); // Tento kód prispel 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 ]--; } // Skopírujte výstupné pole do arr[], takže // arr[] teraz obsahuje zoradené čísla // podľa aktuálnej číslice pre ($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); } // Pomocná funkcia na tlač funkcie poľa 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 pole) { int max = pole[0]; for (final it in array) { if (it> max) { max = it; } } return max; } /// Funkcia na počítanie typu „Zoznam“ [pole] podľa /// číslice reprezentovanej [exp]. Zoznam countSort(Zoznam pole, int exp) { konečná dĺžka = pole.dĺžka; final outputArr = List.filled(length, 0); // Zoznam, kde index predstavuje číslicu a hodnota predstavuje počet // výskytov konečných číslicCount = List.filled(10, 0); // Uloženie počtu výskytov v digitsCount[] for (final item in array) { final digit = item ~/ exp % 10; digitsCount[digit]++; } // Zmeňte digitsCount[i] tak, aby digitsCount[i] teraz obsahoval skutočnú pozíciu // tejto číslice vo 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--) { konečná položka = pole[i]; koncová číslica = položka ~/ exp % 10; outputArr[digitsCount[digit] - 1] = položka; digitsPocet[cisla]--; } return outputArr; } /// Hlavná funkcia, ktorá triedi `List` [pole] pomocou Radix sort List radixSort(Zoznam pole) { // Nájdite maximálny počet, aby ste poznali počet číslic final maxNumber = getMax(pole); // Plytká kópia vstupného poľa final sortArr = List.of(array); // Vykonajte triedenie počítania pre každú číslicu. Všimnite si, že namiesto čísla // čísla sa odovzdáva exp. exp je 10^i, kde i je aktuálne ciferné číslo pre (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortIteration = countSort(sortedArr, exp); sortArr.clear(); sortedArr.addAll(sortedIteration); } return zoradeneArr; } void main() { const pole = [170, 45, 75, 90, 802, 24, 2, 66]; final sortedArray = radixSort(pole); print(sortedArray); } // Tento kód prispel beeduhboodee>
Výkon
2 24 45 66 75 90 170 802>
Analýza zložitosti Radix Sort :
Časová zložitosť:
- Radix sort je nekomparatívny celočíselný triediaci algoritmus, ktorý triedi údaje pomocou celočíselných kľúčov zoskupením kľúčov podľa jednotlivých číslic, ktoré majú rovnakú významnú pozíciu a hodnotu. Má to časovú zložitosť O(d * (n + b)) , kde d je počet číslic, n je počet prvkov a b je základ používanej číselnej sústavy.
- V praktických implementáciách je radixové triedenie často rýchlejšie ako iné triediace algoritmy založené na porovnávaní, ako je rýchle triedenie alebo zlučovacie triedenie, pre veľké množiny údajov, najmä ak majú kľúče veľa číslic. Jeho časová zložitosť však rastie lineárne s počtom číslic, a preto nie je taký efektívny pre malé súbory údajov.
Pomocný priestor:
stiahnite si prehrávač médií youtube vlc
- Radix sort má tiež priestorovú zložitosť O(n + b), kde n je počet prvkov a b je základ číselnej sústavy. Táto priestorová zložitosť pochádza z potreby vytvárať segmenty pre každú číselnú hodnotu a kopírovať prvky späť do pôvodného poľa po zoradení každej číslice.
Často kladené otázky o RadixSort
Q1. Je Radix Sort vhodnejší ako porovnávacie triediace algoritmy, ako je Quick-Sort?
Ak máme log2n bitov na každú číslicu, čas chodu Radixu sa zdá byť lepší ako Quick Sort pre široký rozsah vstupných čísel. Konštantné faktory skryté v asymptotickom zápise sú vyššie pre Radix Sort a Quick-Sort efektívnejšie využíva hardvérové vyrovnávacie pamäte. Radixové triedenie tiež používa triedenie počítania ako podprogram a triedenie počítania zaberá viac miesta na triedenie čísel.
Q2. Čo ak sú prvky v rozsah od 1 do n 2 ?
- Dolná hranica pre porovnávací algoritmus triedenia (Merge Sort, Heap Sort, Quick-Sort .. atď.) je Ω(nLogn), t. j. nemôžu robiť lepšie ako nPrihlásenie . Triedenie počítania je lineárny algoritmus časového triedenia, ktorý triedi v čase O(n+k), keď sú prvky v rozsahu od 1 do k.
- Nemôžeme použiť triedenie počítania, pretože triedenie počítania bude trvať O(n2), čo je horšie ako algoritmy triedenia založené na porovnávaní. Môžeme takéto pole zoradiť v lineárnom čase?
- Zoradiť Radix je odpoveď. Myšlienkou Radix Sort je triediť číslicu po číslici od najmenej významnej číslice po najvýznamnejšiu číslicu. Radix sort používa počítacie triedenie ako podprogram na triedenie.