Ordina radice è un algoritmo di ordinamento lineare che ordina gli elementi elaborandoli cifra per cifra. È un algoritmo di ordinamento efficiente per numeri interi o stringhe con chiavi di dimensione fissa.
Invece di confrontare direttamente gli elementi, Radix Sort distribuisce gli elementi in bucket in base al valore di ciascuna cifra. Ordinando ripetutamente gli elementi in base alle loro cifre significative, dal meno significativo al più significativo, Radix Sort raggiunge l'ordinamento finale.
Algoritmo di ordinamento radicale
L’idea chiave alla base di Radix Sort è sfruttare il concetto di valore posizionale. Si presuppone che l'ordinamento dei numeri cifra per cifra alla fine darà come risultato un elenco completamente ordinato. L'ordinamento digitale può essere eseguito utilizzando diverse varianti, ad esempio l'ordinamento digitale con la cifra meno significativa (LSD) o l'ordinamento digitale con la cifra più significativa (MSD).
Come funziona l'algoritmo Radix Sort?
Per eseguire l'ordinamento digitale sull'array [170, 45, 75, 90, 802, 24, 2, 66], seguiamo questi passaggi:
Come funziona l'algoritmo Radix Sort | Passo 1
Passo 1: Trova l'elemento più grande nell'array, che è 802. Ha tre cifre, quindi ripeteremo tre volte, una per ogni posizione significativa.
Passo 2: Ordina gli elementi in base alle cifre delle unità (X=0). Utilizziamo una tecnica di ordinamento stabile, come l'ordinamento per conteggio, per ordinare le cifre in ciascuna posizione significativa.
perno del server SQLOrdinamento in base al luogo dell'unità:
- Eseguire l'ordinamento del conteggio sull'array in base alle cifre delle posizioni delle unità.
- L'array ordinato in base alla posizione dell'unità è [170, 90, 802, 2, 24, 45, 75, 66].
Come funziona l'algoritmo Radix Sort | Passo 2
Passaggio 3: Ordina gli elementi in base alle cifre delle decine.
Ordinamento in base alle decine:
- Eseguire l'ordinamento del conteggio sull'array in base alle cifre delle decine.
- L'array ordinato in base alle decine è [802, 2, 24, 45, 66, 170, 75, 90].
Come funziona l'algoritmo Radix Sort | Passaggio 3
javaxorPassaggio 4: Ordina gli elementi in base alle cifre delle centinaia.
Ordinamento in base alle centinaia:
- Eseguire l'ordinamento del conteggio sull'array in base alle cifre delle centinaia.
- L'array ordinato in base alle centinaia è [2, 24, 45, 66, 75, 90, 170, 802].
Come funziona l'algoritmo Radix Sort | Passaggio 4
Passaggio 5: L'array è ora ordinato in ordine crescente.
L'array finale ordinato utilizzando l'ordinamento digitale è [2, 24, 45, 66, 75, 90, 170, 802].
Come funziona l'algoritmo Radix Sort | Passaggio 5
Di seguito è riportata l'implementazione delle illustrazioni precedenti:
for loop javaC++
// 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]; restituire mx; } // Una funzione per eseguire il conteggio di arr[] // in base alla cifra // rappresentata da exp. void countSort(int arr[], int n, int exp) { // Array di output int output[n]; int i, conta[10] = { 0 }; // Memorizza il conteggio delle occorrenze // 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[conteggio[(arr[i] / exp) % 10] - 1] = arr[i]; conteggio[(arr[i] / exp) % 10]--; } // Copia l'array di output in arr[], // in modo che arr[] ora contenga numeri ordinati // in base alla cifra corrente per (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); } // Una funzione di utilità per stampare un 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; }> Giava // 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]; restituire mx; } // Una funzione per eseguire il conteggio di arr[] in base // alla cifra rappresentata da exp. static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // array di output int i; int conteggio[] = nuovo int[10]; Arrays.fill(conteggio, 0); // Memorizza il conteggio delle occorrenze 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[conteggio[(arr[i] / exp) % 10] - 1] = arr[i]; conteggio[(arr[i] / exp) % 10]--; } // Copia l'array di output in arr[], in modo che arr[] ora // contenga numeri ordinati in base alla // cifra corrente per (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); } // Una funzione di utilità per stampare un 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: indice = arr[i] // exp1 output[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # Copia l'array di output in arr[] , # in modo che arr ora contenga numeri ordinati i = 0 for i in range(0, len(arr)): arr[i] = output[i] # Metodo per eseguire Radix Sort def radixSort(arr): # Trova il massimo numero per conoscere il numero di cifre max1 = max(arr) # Esegue l'ordinamento del conteggio per ogni cifra. Si noti che invece di # passare il numero della cifra, viene passato exp. exp è 10^i # dove i è il numero della cifra corrente exp = 1 while max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Codice driver arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funzione Call radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # Questo codice è un contributo di Mohit Kumra # Modificato da 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]; restituire mx; } // Una funzione per eseguire il conteggio di arr[] in base // alla cifra rappresentata da exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // array di output int i; int[] conteggio = nuovo int[10]; // inizializza tutti gli elementi di count a 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[conteggio[(arr[i] / exp) % 10] - 1] = arr[i]; conteggio[(arr[i] / exp) % 10]--; } // Copia l'array di output in arr[], in modo che arr[] ora // contenga numeri ordinati in base alla // cifra corrente per (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); } // Una funzione di utilità per stampare un 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]; } restituisce mx; } // Una funzione per eseguire il conteggio di arr[] in base // alla cifra rappresentata da exp. function countSort(arr, exp) { const length = arr.length; let output = Array(lunghezza); // array di output let count = Array(10).fill(0, 0); // Memorizza il conteggio delle occorrenze in count[] for (let 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[conteggio[cifra] - 1] = arr[i]; contare[cifra]--; } restituisce l'output; } // La funzione principale che ordina arr[] utilizzando la funzione Radix Sort radixSort(arr) { // Trova il numero massimo per conoscere il numero di cifre const maxNumber = getMax(arr); // Crea una copia superficiale in cui verranno mantenuti i valori ordinati let sortedArr = [...arr]; // Esegue l'ordinamento dei conteggi per ogni cifra. Si noti che // invece di passare il numero della cifra, viene passato l'exp. // exp è 10^i dove i è il numero della cifra corrente per (let exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Ottieni l'iterazione di ordinamento Count const sortedIteration = countSort(sortedArr , esp); sortedArr = sortedIterazione; } restituisce sortedArr; } /*Codice driver*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Chiamata di funzione const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Questo codice è un contributo di 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[$conteggio[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $conteggio[ ($arr[$i] / $exp) % 10 ]--; } // Copia l'array di output in arr[], in modo che // arr[] ora contenga numeri ordinati // in base alla cifra corrente per ($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); } // Una funzione di utilità per stampare un array funzione 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 ?>> Dardo // 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 nell'array) { if (it> max) { max = it; } } restituisce massimo; } /// Una funzione per eseguire il conteggio di `List` [array] in base alla /// cifra rappresentata da [exp]. Elenco countSort(Lista array, int exp) { lunghezza finale = array.lunghezza; outputArr finale = List.filled(length, 0); // Un elenco in cui indice rappresenta la cifra e valore rappresenta il conteggio delle // occorrenze final digitsCount = List.filled(10, 0); // Memorizza il conteggio delle occorrenze in digitsCount[] for (elemento finale nell'array) { cifra finale = elemento ~/ exp % 10; cifreConta[cifra]++; } // Cambia digitsCount[i] in modo che digitsCount[i] ora contenga la posizione effettiva // di questa cifra in 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--) { elemento finale = array[i]; cifra finale = voce ~/exp % 10; outputArr[digitsCount[cifra] - 1] = articolo; cifreConteggio[cifra]--; } restituisce outputArr; } /// La funzione principale che ordina un `List` [array] utilizzando Radix sort List radixSort(Lista array) { // Trova il numero massimo per conoscere il numero di cifre final maxNumber = getMax(array); // Copia superficiale dell'array di input final sortedArr = List.of(array); // Esegue l'ordinamento dei conteggi per ogni cifra. Tieni presente che invece di passare digit // number, viene passato exp. exp è 10^i, dove i è il numero della cifra corrente per (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); sortedArr.clear(); sortedArr.addAll(sortedIteration); } restituisce sortedArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; final sortedArray = radixSort(array); print(array ordinato); } // Questo codice è un contributo di beeduhboodee>
Produzione
2 24 45 66 75 90 170 802>
Analisi della complessità del Radix Sort :
Complessità temporale:
- L'ordinamento radicale è un algoritmo di ordinamento di numeri interi non comparativo che ordina i dati con chiavi intere raggruppando le chiavi in base alle singole cifre che condividono la stessa posizione e valore significativi. Ha una complessità temporale di O(d * (n + b)) , dove d è il numero di cifre, n è il numero di elementi e b è la base del sistema numerico utilizzato.
- Nelle implementazioni pratiche, l'ordinamento digitale è spesso più veloce di altri algoritmi di ordinamento basati sul confronto, come Quicksort o Merge Sort, per insiemi di dati di grandi dimensioni, soprattutto quando le chiavi hanno molte cifre. Tuttavia, la sua complessità temporale cresce linearmente con il numero di cifre e quindi non è altrettanto efficiente per set di dati di piccole dimensioni.
Spazio ausiliario:
- Anche l'ordinamento radicale ha una complessità spaziale di O(n+b), dove n è il numero di elementi e b è la base del sistema numerico. Questa complessità spaziale deriva dalla necessità di creare contenitori per ogni valore di cifra e di copiare nuovamente gli elementi nell'array originale dopo che ogni cifra è stata ordinata.
Domande frequenti su RadixSort
Q1. Radix Sort è preferibile agli algoritmi di ordinamento basati sul confronto come Quick-Sort?
Se abbiamo log2n bit per ogni cifra, il tempo di esecuzione di Radix sembra essere migliore di Quick Sort per un'ampia gamma di numeri di input. I fattori costanti nascosti nella notazione asintotica sono più alti per Radix Sort e Quick-Sort utilizza le cache hardware in modo più efficace. Inoltre, l'ordinamento radicale utilizza l'ordinamento di conteggio come subroutine e l'ordinamento di conteggio richiede spazio aggiuntivo per ordinare i numeri.
Q2. E se gli elementi fossero nel file vanno da 1 a n 2 ?
- Il limite inferiore per l'algoritmo di ordinamento basato sul confronto (Merge Sort, Heap Sort, Quick-Sort .. ecc.) è Ω(nLogn), ovvero non possono fare meglio di nAccedi . L'ordinamento di conteggio è un algoritmo di ordinamento temporale lineare che ordina in tempo O(n+k) quando gli elementi sono compresi nell'intervallo da 1 a k.
- Non possiamo usare l'ordinamento per conteggio perché l'ordinamento per conteggio richiederà O(n2) che è peggiore degli algoritmi di ordinamento basati sul confronto. Possiamo ordinare un tale array in tempo lineare?
- Ordina radice è la risposta. L'idea di Radix Sort è di eseguire l'ordinamento cifra per cifra partendo dalla cifra meno significativa fino a quella più significativa. L'ordinamento radicale utilizza l'ordinamento di conteggio come subroutine per l'ordinamento.