// 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];  atgriešanās mx; } // Funkcija, lai veiktu skaitīšanas veidu arr[] // atbilstoši ciparam //, ko apzīmē ar exp. void countSort(int arr[], int n, int exp) { // Izvades masīvs int izvade[n];  int i, skaits[10] = {0};  // Saglabāt gadījumu skaitu // 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--) { izvade[skaits[(arr[i] / exp) % 10] - 1] = arr[i];  count [(arr[i] / exp) % 10]--;  } // Kopējiet izvades masīvu uz arr[], // lai arr[] tagad saturētu sakārtotus // numurus atbilstoši pašreizējam ciparam (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); } // Lietderības funkcija masīva drukāšanai 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];  atgriešanās mx;  } // Funkcija, lai veiktu skaitīšanas veidu arr[] atbilstoši // ciparam, ko attēlo exp.  static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // izvades masīvs int i;  int skaits[] = jauns int[10];  Arrays.fill(count, 0);  // Saglabāt gadījumu skaitu count[], ja (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--) { izvade[skaits[(arr[i] / exp) % 10] - 1] = arr[i];  count [(arr[i] / exp) % 10]--;  } // Kopējiet izvades masīvu uz arr[], lai arr[] tagad // saturētu skaitļus, kas sakārtoti atbilstoši pašreizējam // ciparam (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);  } // Lietderības funkcija, lai drukātu masīvu statisku 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: indekss = arr[i] // exp1 izvade[skaits[indekss % 10] - 1] = arr[i] skaits[indekss % 10] -= 1 i -= 1 # Izvades masīva kopēšana uz arr[] , # lai arr tagad saturētu sakārtotus skaitļus i = 0 diapazonā(0, len(arr)): arr[i] = output[i] # Metode, kā rīkoties Radix Kārtot def radixSort(arr): # Atrast maksimālo numurs, lai uzzinātu ciparu skaitu max1 = max(arr) # Veiciet skaitīšanas kārtošanu katram ciparam. Ņemiet vērā, ka tā vietā, lai ievadītu cipara skaitli, tiek nodots exp. exp ir 10^i # kur i ir pašreizējais cipara skaitlis exp = 1, savukārt max1 / exp>= 1: skaitīšana Kārtot(arr, exp) exp *= 10 # Draivera kods arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funkciju izsaukums radixSort(arr) for i diapazonā(len(arr)): print(arr[i], end=' ') # Šo kodu ir sagatavojis Mohits Kumra # Rediģējis Patriks Galahers>>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; } // Funkcija, lai veiktu skaitīšanas veidu arr[] atbilstoši // ciparam, ko attēlo exp. function countSort(arr, exp) { const garums = arr.length;  let output = Masīvs(garums); // izvades masīvs let count = Array(10).fill(0, 0);  // Saglabāt gadījumu skaitu count[] for (lai 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 cipars = Math.floor(arr[i] / exp) % 10;  izvade[skaits[cipars] ​​- 1] = arr[i];  skaits[cipars]--;  } atgriezt izvadi; } // Galvenā funkcija, kas kārto arr[], izmantojot Radix Sort funkciju radixSort(arr) { // Atrast maksimālo skaitu, lai uzzinātu ciparu skaitu const maxNumber = getMax(arr);  // Izveidojiet seklu kopiju, kurā tiks saglabātas sakārtotās vērtības let sortedArr = [...arr];  // Veiciet skaitīšanas kārtošanu katram ciparam. Ņemiet vērā, ka // tā vietā, lai nodotu cipara skaitli, tiek nodots exp.  // exp ir 10^i kur i ir pašreizējais cipara skaitlis (lai exp = 1; Math.floor(maksimālais skaits / exp)> 0; exp *= 10) { // Iegūt Count kārtošanas iterāciju const sortedIteration = countSort(sortedArr , exp);  sortedArr = sortedIteration;  } return sortedArr; } /*Driver Code*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funkcija Call const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Šo kodu ir sagatavojis 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--) { $izvads[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // Kopējiet izvades masīvu uz arr[], tāpēc // šajā arr[] tagad ir sakārtoti skaitļi // atbilstoši pašreizējam ciparam ($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); } // Lietderības funkcija masīva funkcijas drukāšanai 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 ?>>>Šautriņa2 24 45 66 75 90 170 802>

Radix šķirošanas sarežģītības analīze :

Laika sarežģītība:

• Radix šķirošana ir nesalīdzinošs veselu skaitļu kārtošanas algoritms, kas kārto datus ar veselu skaitļu atslēgām, grupējot atslēgas pēc atsevišķiem cipariem, kuriem ir vienāda nozīmīga pozīcija un vērtība. Tam ir laika sarežģītība O(d * (n + b)) , kur d ir ciparu skaits, n ir elementu skaits un b ir izmantotās skaitļu sistēmas bāze.
• Praktiskajās ieviesumos lielām datu kopām radix kārtošana bieži ir ātrāka nekā citi uz salīdzināšanu balstīti kārtošanas algoritmi, piemēram, ātrā kārtošana vai sapludināšanas kārtošana, it īpaši, ja taustiņiem ir daudz ciparu. Tomēr tā laika sarežģītība pieaug lineāri līdz ar ciparu skaitu, un tāpēc tas nav tik efektīvs mazām datu kopām.

Palīgtelpa:

• Radix sort ir arī telpas sarežģītība O(n+b), kur n ir elementu skaits un b ir skaitļu sistēmas bāze. Šīs telpas sarežģītības iemesls ir nepieciešamība izveidot segmentus katrai cipara vērtībai un kopēt elementus atpakaļ sākotnējā masīvā pēc katra cipara sakārtošanas.

Bieži uzdotie jautājumi par RadixSort

Q1. Vai Radix Sort ir labāka par salīdzināšanu balstītiem šķirošanas algoritmiem, piemēram, Quick-Sort?

Ja mums ir žurnāls₂n biti katram ciparam, Radix darbības laiks, šķiet, ir labāks nekā ātrā kārtošana plašam ievades skaitļu diapazonam. Pastāvīgie faktori, kas paslēpti asimptotiskajā apzīmējumā, ir lielāki Radix Sort un Quick-Sort efektīvāk izmanto aparatūras kešatmiņas. Turklāt Radix sort izmanto skaitīšanas kārtošanu kā apakšprogrammu, un skaitīšanas kārtošana aizņem papildu vietu skaitļu kārtošanai.

Q2. Ko darīt, ja elementi atrodas diapazonā no 1 līdz n ² ?

pandas un numpy

• Apakšējā robeža uz salīdzinājumu balstītā šķirošanas algoritma (apvienošanas kārtošana, kaudzes kārtošana, ātrā kārtošana .. utt.) ir Ω (nLogn), t.i., tie nevar darboties labāk nekā nPieteikties . Skaitīšanas kārtošana ir lineāra laika šķirošanas algoritms, kas kārto O(n+k) laikā, kad elementi ir diapazonā no 1 līdz k.
• Mēs nevaram izmantot skaitīšanas kārtošanu, jo skaitīšanas kārtošanai būs nepieciešams O(n²), kas ir sliktāks nekā uz salīdzināšanu balstīti šķirošanas algoritmi. Vai mēs varam sakārtot šādu masīvu lineārajā laikā?
  • Kārtot Radix ir atbilde. Radix Sort ideja ir veikt kārtošanu pa cipariem, sākot no vismazākā cipara līdz visnozīmīgākajam ciparam. Radix sort izmanto skaitīšanas kārtošanu kā kārtošanas apakšprogrammu.