// 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];  return mx; } // O funcție pentru a face numărare sort de arr[] // în funcție de cifra // reprezentată de exp. void countSort(int arr[], int n, int exp) { // Ieșire matrice int output[n];  int i, count[10] = { 0 };  // Stochează numărul de apariții // în count[] pentru (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]--;  } // Copiați tabloul de ieșire în arr[], // astfel încât arr[] să conțină acum numere sortate // conform cifrei curente pentru (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); } // O funcție utilitar pentru a tipări o matrice 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; }>

// 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];  return mx;  } // O funcție pentru a face numărare sortare de arr[] în funcție de // cifra reprezentată de exp.  static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // matrice de ieșire int i;  int count[] = new int[10];  Arrays.fill(număr, 0);  // Stochează numărul de apariții în count[] pentru (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]--;  } // Copiați tabloul de ieșire în arr[], astfel încât arr[] acum // să conțină numere sortate în funcție de cifra curentă // pentru (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);  } // O funcție utilitar pentru a imprima o matrice 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 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 # Copierea matricei de ieșire în arr[] , # astfel încât arr să conțină acum numere sortate i = 0 pentru i în intervalul(0, len(arr)): arr[i] = output[i] # Metoda de a face Radix Sort def radixSort(arr): # Găsiți valoarea maximă număr pentru a ști numărul de cifre max1 = max(arr) # Efectuați sortarea numărării pentru fiecare cifră. Rețineți că în loc de # de numărul de cifre care trece, se trece exp. exp este 10^i # unde i este numărul cifrei curente exp = 1 în timp ce max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Cod driver arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funcție Apelați radixSort(arr) pentru i în interval(len(arr)): print(arr[i], end=' ') # Acest cod este contribuit de Mohit Kumra # Editat de Patrick Gallagher>>>C#

// 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; } // O funcție pentru a face numărare sortare de arr[] în funcție de // cifra reprezentată de exp. function countSort(arr, exp) { const length = arr.length;  let output = Array(lungime); // matrice de ieșire let count = Array(10).fill(0, 0);  // Stochează numărul de apariții în count[] for (fie 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;  ieșire[număr[cifră] - 1] = arr[i];  numără[cifră]--;  } returnare ieșire; } // Funcția principală care sortează arr[] folosind funcția Radix Sort radixSort(arr) { // Găsiți numărul maxim de știut numărul de cifre const maxNumber = getMax(arr);  // Creați o copie mică unde valorile sortate vor fi păstrate let sortedArr = [...arr];  // Faceți sortarea numărării pentru fiecare cifră. Rețineți că // în loc de a trece un număr de cifre, se trece exp.  // exp este 10^i unde i este numărul curent al cifrei pentru (fie exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Obține iterația de sortare Count const sortdIteration = countSort(sortedArr , exp);  sortedArr = sortatIteration;  } return sortedArr; } /*Cod șofer*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Apelul funcției const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Acest cod este contribuit de beeduhboodee>

 // 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--) { $ieșire[$număr[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $număr[ ($arr[$i] / $exp) % 10 ]--; } // Copiați tabloul de ieșire în arr[], deci // că arr[] conține acum numere sortate // conform cifrei curente pentru ($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); } // O funcție utilitar pentru a tipări o funcție matrice PrintArray(&$arr,$n) { pentru ($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 ?>>>>Lance2 24 45 66 75 90 170 802>

Analiza complexității sortării Radix :

Complexitatea timpului:

• Radix sort este un algoritm de sortare a numerelor întregi non-comparativ care sortează datele cu chei întregi prin gruparea cheilor după cifrele individuale care au aceeași poziție și valoare semnificativă. Are o complexitate de timp de O(d * (n + b)) , unde d este numărul de cifre, n este numărul de elemente și b este baza sistemului numeric utilizat.
• În implementările practice, sortarea radix este adesea mai rapidă decât alți algoritmi de sortare bazați pe comparație, cum ar fi sortarea rapidă sau sortarea prin îmbinare, pentru seturi mari de date, mai ales când cheile au multe cifre. Cu toate acestea, complexitatea sa de timp crește liniar cu numărul de cifre și, prin urmare, nu este la fel de eficient pentru seturile de date mici.

Spațiu auxiliar:

• Sortarea Radix are, de asemenea, o complexitate spațială de O(n + b), unde n este numărul de elemente și b este baza sistemului numeric. Această complexitate spațială vine din necesitatea de a crea găleți pentru fiecare valoare de cifră și de a copia elementele înapoi în matricea originală după ce fiecare cifră a fost sortată.

Întrebări frecvente despre RadixSort

Î1. Este Radix Sort de preferat algoritmilor de sortare bazați pe comparație, cum ar fi Quick-Sort?

Dacă avem log₂n biți pentru fiecare cifră, timpul de rulare al lui Radix pare a fi mai bun decât Sortarea rapidă pentru o gamă largă de numere de intrare. Factorii constanți ascunși în notația asimptotică sunt mai mari pentru Radix Sort și Quick-Sort utilizează cache-urile hardware mai eficient. De asemenea, sortarea Radix folosește sortarea de numărare ca subrutină, iar sortarea de numărare ocupă spațiu suplimentar pentru sortarea numerelor.

Q2. Ce se întâmplă dacă elementele sunt în interval de la 1 la n ² ?

genericitate în java

• Limita inferioară pentru algoritmul de sortare bazat pe comparație (Merge Sort, Heap Sort, Quick-Sort .. etc) este Ω(nLogn), adică nu pot face mai bine decât nLogin . Sortarea de numărare este un algoritm de sortare liniară în timp care sortează în timp O(n+k) atunci când elementele sunt în intervalul de la 1 la k.
• Nu putem folosi sortarea de numărare, deoarece sortarea de numărare va lua O(n²) care este mai rău decât algoritmii de sortare bazați pe comparație. Putem sorta o astfel de matrice în timp liniar?
  • Sort Radix este raspunsul. Ideea lui Radix Sort este de a face sortarea cifră cu cifră, începând de la cifra cea mai puțin semnificativă până la cea mai semnificativă cifră. Sortarea Radix folosește sortarea numărătoare ca subrutină pentru sortare.