Radix Sort és un algorisme d'ordenació lineal que ordena els elements processant-los dígit per dígit. És un algorisme d'ordenació eficient per a nombres enters o cadenes amb claus de mida fixa.
En lloc de comparar elements directament, Radix Sort distribueix els elements en cubs en funció del valor de cada dígit. En ordenar repetidament els elements segons els seus dígits significatius, des del menys significatiu al més significatiu, Radix Sort aconsegueix l'ordre ordenat final.
Algoritme d'ordenació de la base
La idea clau darrere de Radix Sort és explotar el concepte de valor posicional. Se suposa que ordenar els números dígit per dígit finalment donarà lloc a una llista completament ordenada. L'Ordenació Radix es pot realitzar mitjançant diferents variacions, com ara l'Ordenació Radix Least Digit Significant (LSD) o la Classificació Radix Digit Most Significant (MSD).
Com funciona l'algoritme d'ordenació de Radix?
Per fer l'ordenació radix a la matriu [170, 45, 75, 90, 802, 24, 2, 66], seguim aquests passos:
Com funciona l'algoritme d'ordenació de Radix | Pas 1
Pas 1: Trobeu l'element més gran de la matriu, que és 802. Té tres dígits, així que repetirem tres vegades, una vegada per cada lloc significatiu.
Pas 2: Ordena els elements segons els dígits de la unitat (X=0). Utilitzem una tècnica d'ordenació estable, com ara l'ordenació per recompte, per ordenar els dígits a cada lloc significatiu.
mysql llista tots els usuarisClassificació segons el lloc de la unitat:
- Realitzeu l'ordenació de recompte a la matriu en funció dels dígits del lloc de la unitat.
- La matriu ordenada segons el lloc de la unitat és [170, 90, 802, 2, 24, 45, 75, 66].
Com funciona l'algoritme d'ordenació de Radix | Pas 2
Pas 3: Ordena els elements segons els dígits de les desenes.
Ordenació segons el lloc de les desenes:
- Feu l'ordenació de recompte a la matriu en funció dels dígits de les desenes.
- La matriu ordenada basada en el lloc de les desenes és [802, 2, 24, 45, 66, 170, 75, 90].
Com funciona l'algoritme d'ordenació de Radix | Pas 3
10 de 40Pas 4: Ordena els elements en funció dels dígits de les centenes.
Classificació segons el lloc de les centenes:
- Realitzeu l'ordenació de recompte a la matriu en funció dels centenars de dígits de lloc.
- La matriu ordenada basada en el lloc de les centenes és [2, 24, 45, 66, 75, 90, 170, 802].
Com funciona l'algoritme d'ordenació de Radix | Pas 4
Pas 5: La matriu s'ordena ara en ordre ascendent.
La matriu ordenada final utilitzant l'ordenació radix és [2, 24, 45, 66, 75, 90, 170, 802].
Com funciona l'algoritme d'ordenació de Radix | Pas 5
A continuació es mostra la implementació de les il·lustracions anteriors:
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]; retorn mx; } // Una funció per fer el recompte tipus arr[] // segons el dígit // representat per exp. void countSort(int arr[], int n, int exp) { // Sortida matriu int sortida[n]; int i, comptar[10] = {0}; // Emmagatzema el recompte d'ocurrències // a count[] per a (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--) { sortida[compte[(arr[i] / exp) % 10] - 1] = arr[i]; recompte[(arr[i] / exp) % 10]--; } // Copieu la matriu de sortida a arr[], // de manera que arr[] ara contingui // nombres ordenats segons el dígit actual 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 funció d'utilitat per imprimir una matriu 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]; retorn mx; } // Una funció per fer un recompte tipus arr[] segons // el dígit representat per exp. static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // matriu de sortida int i; int count[] = nou int[10]; Arrays.fill(compte, 0); // Emmagatzema el recompte d'ocurrències a count[] per a (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--) { sortida[compte[(arr[i] / exp) % 10] - 1] = arr[i]; recompte[(arr[i] / exp) % 10]--; } // Copieu la matriu de sortida a arr[], de manera que arr[] ara // contingui nombres ordenats segons el // dígit actual de (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 funció d'utilitat per imprimir una matriu 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); } }> Python 3 # 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: índex = arr[i] // exp1 sortida[compte[índex % 10] - 1] = arr[i] recompte[índex % 10] -= 1 i -= 1 # S'està copiant la matriu de sortida a arr[] , # de manera que ara arr conté nombres ordenats i = 0 per a i dins l'interval (0, len(arr)): arr[i] = sortida[i] # Mètode per fer Radix Sort def radixSort(arr): # Troba el màxim nombre per saber el nombre de dígits max1 = max(arr) # Feu l'ordenació de recompte per a cada dígit. Tingueu en compte que en lloc de # de passar el número de dígit, es passa exp. exp és 10^i # on i és el número de dígits actual exp = 1 mentre que max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Codi del controlador arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Crida a la funció radixSort(arr) per a i en rang(len(arr)): print(arr[i], end=' ') # Aquest codi és aportat per Mohit Kumra # Editat per Patrick Gallagher>>>C#
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]; } retorn mx; } // Una funció per fer un recompte tipus arr[] segons // el dígit representat per exp. function countSort(arr, exp) { const length = arr.length; deixar sortida = Matriu (longitud); // matriu de sortida let count = Array(10).fill(0, 0); // Emmagatzema el recompte d'ocurrències a count[] per (deixa 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--) { dígit constant = Math.floor(arr[i] / exp) % 10; sortida[compte[dígit] - 1] = arr[i]; comptar[dígit]--; } retorn de sortida; } // La funció principal que ordena arr[] utilitzant la funció Radix Sort radixSort(arr) { // Troba el nombre màxim per saber el nombre de dígits const maxNumber = getMax(arr); // Crea una còpia poc profunda on es mantindran els valors ordenats let sortedArr = [...arr]; // Fes l'ordenació de recompte per a cada dígit. Tingueu en compte que // en comptes de passar el número de dígit, es passa exp. // exp és 10^i on i és el número de dígit actual per a (deixar exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Obteniu la iteració d'ordenació de recompte const sortedIteration = countSort(sortedArr , exp); sortedArr = Iteració ordenada; } retorn ordenatArr; } /*Codi del conductor*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Crida a la funció const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Aquest codi és aportat per beeduhboodee>>>PHP> Dard // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List matriu) { int max = matriu[0]; for (final it a array) { if (it> max) { max = it; } } retorn màxim; } /// Una funció per fer un recompte de `Lista` [matriu] segons el dígit /// representat per [exp]. Llista countSort(Llista array, int exp) { longitud final = array.length; final outputArr = List.filled (longitud, 0); // Una llista on index representa el dígit i el valor representa el recompte d'ocurrències final digitsCount = List.filled(10, 0); // Emmagatzema el recompte d'ocurrències a digitsCount[] for (element final a la matriu) { final digit = item ~/ exp % 10; digitsCount[dígit]++; } // Canvia digitsCount[i] de manera que digitsCount[i] ara contingui la posició real // d'aquest dígit a outputArr[] per (int i = 1; i< 10; i++) { digitsCount[i] += digitsCount[i - 1]; } // Build the output array for (int i = length - 1; i>= 0; i--) { element final = matriu[i]; dígit final = element ~/ exp % 10; outputArr[digitsCount[dígit] - 1] = element; digitsCount[dígit]--; } retornar outputArr; } /// La funció principal que ordena una `Lista` [matriu] utilitzant la llista d'ordenació de Radix radixSort(Llista array) { // Troba el nombre màxim per saber el nombre de dígits final maxNumber = getMax(array); // Còpia superficial de la matriu d'entrada final sortedArr = List.of(array); // Fes l'ordenació de recompte per a cada dígit. Tingueu en compte que en lloc de passar el dígit // nombre, es passa exp. exp és 10^i, on i és el número de dígit actual per a (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortdIteration = countSort(sortedArr, exp); ordenatArr.clear(); sortedArr.addAll(sortedIteration); } retorn ordenatArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66]; sortdArray final = radixSort (matriu); imprimir (sortedArray); } // Aquest codi és aportat per beeduhboodee>
Sortida
2 24 45 66 75 90 170 802>
Anàlisi de complexitat de Radix Sort :
Complexitat temporal:
- L'ordenació de radix és un algorisme d'ordenació de nombres enters no comparatiu que ordena les dades amb claus senceres agrupant les claus per dígits individuals que comparteixen la mateixa posició i valor significatius. Té una complexitat temporal de O(d * (n + b)) , on d és el nombre de dígits, n és el nombre d'elements i b és la base del sistema de numeració que s'utilitza.
- En implementacions pràctiques, l'ordenació radix és sovint més ràpida que altres algorismes d'ordenació basats en comparacions, com ara quicksort o merge sort, per a grans conjunts de dades, especialment quan les claus tenen molts dígits. Tanmateix, la seva complexitat temporal creix linealment amb el nombre de dígits, de manera que no és tan eficient per a conjunts de dades petits.
Espai auxiliar:
- Radix sort també té una complexitat espacial de O (n + b), on n és el nombre d'elements i b és la base del sistema numèric. Aquesta complexitat espacial prové de la necessitat de crear cubs per a cada valor de dígit i copiar els elements de nou a la matriu original després d'haver ordenat cada dígit.
Preguntes freqüents sobre RadixSort
Q1. És preferible Radix Sort als algorismes d'ordenació basats en la comparació com Quick-Sort?
Si tenim registre2n bits per cada dígit, el temps d'execució de Radix sembla ser millor que l'Ordenació ràpida per a una àmplia gamma de números d'entrada. Els factors constants amagats en la notació asimptòtica són més alts per a Radix Sort i Quick-Sort utilitza la memòria cau de maquinari de manera més eficaç. A més, l'ordenació Radix utilitza l'ordenació de recompte com a subrutina i l'ordenació de recompte ocupa un espai addicional per ordenar els números.
gimp eliminant el fons
P2. Què passa si els elements estan a la van d'1 a n 2 ?
- El límit inferior per a l'algorisme d'ordenació basat en la comparació (ordenació combinada, ordenació munt, ordenació ràpida .. etc.) és Ω(nLogn), és a dir, no poden fer-ho millor que n Inici de sessió . L'ordenació de comptatge és un algorisme d'ordenació temporal lineal que ordena en temps O(n+k) quan els elements es troben en el rang d'1 a k.
- No podem utilitzar l'ordenació per recompte perquè l'ordenació per recompte prendrà O (n2), que és pitjor que els algorismes d'ordenació basats en comparacions. Podem ordenar aquesta matriu en temps lineal?
- Radix Sort és la resposta. La idea de Radix Sort és fer una classificació dígit per dígit començant des del dígit menys significatiu fins al dígit més significatiu. L'ordenació Radix utilitza l'ordenació de recompte com a subrutina per ordenar.