Radix sort
Ultimo aggiornamento
Il radix sort è un ordinamento non basato sui confronti per numeri interi. Invece di confrontare i valori, ordina i numeri cifra per cifra. La versione LSD (dalla cifra meno significativa) elabora prima le unità, poi le decine, poi le centinaia, usando un counting sort stabile per ogni cifra. Dato che ogni passata è stabile, una volta elaborata la cifra più significativa l'intero array è ordinato. Premi play qui sopra per vedere ogni passata sulle cifre riordinare le barre.
Il radix sort richiede tempo O(d·(n + k)), dove d è il numero di cifre e k la base (qui 10). Per interi a larghezza fissa è di fatto lineare e può battere gli ordinamenti per confronto O(n log n), ma funziona solo su dati che si possono scomporre in cifre o chiavi.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Tempo | O(d·(n + k)) | d cifre, base k (lineare per d fisso) |
| Spazio | O(n + k) | Array di output + conteggi delle cifre |
| Stabile | Sì | Ogni passata sulle cifre è un counting sort stabile |
| Per confronto? | No | Ordina per cifra, non confrontando i valori |
| Funziona su | Interi/chiavi | Non su oggetti confrontabili generici |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Trova il valore massimo per sapere quante cifre elaborare. |
| 2 | Parti dalla cifra meno significativa (le unità). |
| 3 | Ordina l'array in modo stabile in base a quella cifra usando il counting sort. |
| 4 | Passa alla cifra successiva, più significativa. |
| 5 | Ripeti finché tutte le posizioni delle cifre non sono elaborate. |
Esempio svolto
Ordinamento di [170, 45, 75, 90, 2, 24, 66]:
| Passata | Array | Azione |
|---|---|---|
| Inizio | [170, 45, 75, 90, 2, 24, 66] | Il massimo è 170, quindi servono tre passate sulle cifre. |
| Unità | [170, 90, 2, 24, 45, 75, 66] | Ordinamento stabile per la cifra delle unità: 0, 0, 2, 4, 5, 5, 6. |
| Decine | [2, 24, 45, 66, 170, 75, 90] | Ordinamento stabile per la cifra delle decine: 0, 2, 4, 6, 7, 7, 9 (170 resta davanti a 75). |
| Centinaia | [2, 24, 45, 66, 75, 90, 170] | Ordinamento stabile per la cifra delle centinaia; solo 170 ha un 1, quindi va in fondo. Ordinato. |
Quando usare il radix sort
| Usalo quando | Evitalo quando |
|---|---|
| Le chiavi sono interi o stringhe a lunghezza fissa che puoi scomporre in cifre. | Devi ordinare oggetti arbitrari con un comparatore personalizzato. |
Le chiavi hanno un numero di cifre d piccolo e limitato, quindi O(d·(n + k)) batte O(n log n). | Le chiavi sono molto lunghe o illimitate, rendendo d grande e le passate costose. |
Ti serve un ordinamento stabile e puoi permetterti O(n + k) di spazio extra. | La memoria è poca e i buffer O(n + k) non sono accettabili. |
L'intervallo dei valori o la base k è contenuto rispetto a n. | k è enorme, quindi ogni passata di counting sort domina il tempo di esecuzione. |
Codice Radix Sort
Un'implementazione di Radix Sort pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Radix Sort in Python
Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))Codice Radix Sort in JavaScript
JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Codice Radix Sort in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}Codice Radix Sort in C++
C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Codice Radix Sort in C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Domande frequenti sul radix sort
Qual è la complessità temporale del radix sort?
Il radix sort è
O(d·(n + k)), dove d è il numero di cifre e k la base. Per interi a larghezza fissa è di fatto O(n), e può essere più veloce degli ordinamenti per confronto. Usa O(n + k) di spazio extra.Il radix sort è stabile?
Sì. Il radix sort LSD si basa su un counting sort stabile per ogni cifra; è proprio la stabilità a far sì che l'approccio cifra per cifra produca un risultato ordinato correttamente.
Quando posso usare il radix sort?
Il radix sort funziona su dati scomponibili in cifre o chiavi a dimensione fissa, come interi o stringhe a lunghezza fissa. Non è un ordinamento per confronto generico, quindi non può ordinare oggetti arbitrari con un comparatore personalizzato.
In cosa il radix sort è diverso dal counting sort?
Il counting sort ordina in base a una sola chiave in una passata e ha bisogno di un array dei conteggi grande quanto l'intervallo dei valori, quindi peggiora quando i valori sono molto sparsi. Il radix sort applica il counting sort cifra per cifra, mantenendo piccolo l'array dei conteggi di ogni passata (base
k), e così gestisce grandi intervalli di valori che un semplice counting sort non potrebbe gestire.Perché il radix sort LSD parte dalla cifra meno significativa?
Partire dalla cifra meno significativa permette a ogni passata stabile di preservare l'ordine stabilito da tutte le cifre precedenti, meno significative. Quando si arriva alla cifra più significativa, i pareggi su quella cifra sono già ordinati correttamente dalle cifre inferiori, quindi l'array risulta completamente ordinato. Partire dalla cifra più significativa romperebbe questo meccanismo e richiederebbe un approccio diverso e ricorsivo (radix sort MSD).
Il radix sort gestisce i numeri negativi?
Non direttamente: l'estrazione base delle cifre presuppone interi non negativi. Le soluzioni comuni sono spostare tutti i valori sommando il minimo in modo che siano tutti non negativi, oppure ordinare separatamente negativi e non negativi e poi concatenarli. Ignorare questo aspetto è un bug frequente quando si applica il radix sort a dati reali.
Risorse correlate
Altre visualizzazioni
