// 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];  paluu mx; } // Funktio, joka tekee laskentatapaa arr[] // exp:n edustaman luvun // mukaan. void countSort(int arr[], int n, int exp) { // Lähtötaulukko int lähtö[n];  int i, count[10] = { 0 };  // Tallenna esiintymien lukumäärä // 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--) { tulos[määrä[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Kopioi tuloste taulukkoon arr[], // niin että arr[] sisältää nyt lajiteltuja // numeroita nykyisen numeron mukaan (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); } // Aputoiminto taulukon tulostamiseen 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];  paluu mx;  } // Funktio, joka laskee eräänlaisen arr[] // exp:n edustaman numeron mukaan.  staattinen void count Lajittele(int arr[], int n, int exp) { int lähtö[] = uusi int[n]; // tulostustaulukko int i;  int count[] = uusi int[10];  Arrays.fill(count, 0);  // Tallenna esiintymien lukumäärä count[]:lle kohteelle (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--) { tulos[määrä[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Kopioi tuloste taulukkoon arr[], jotta arr[] nyt // sisältää lajiteltuja numeroita nykyisen // numeron mukaan (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);  } // Aputoiminto taulukon tulostamiseen staattinen 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: indeksi = arr[i] // exp1 lähtö[luku[indeksi % 10] - 1] = arr[i] määrä[indeksi % 10] -= 1 i -= 1 # Tulostustaulukon kopioiminen arr[] , # niin, että arr sisältää nyt lajiteltuja lukuja i = 0 i:lle alueella(0, len(arr)): arr[i] = output[i] # Menetelmä Radix Sort def radixSort(arr): # Etsi maksimi numero tiedossa numeroiden lukumäärä max1 = max(arr) # Suorita laskennallinen lajittelu jokaiselle numerolle. Huomaa, että numeron # sijaan välitetään exp. exp on 10^i # missä i on nykyinen numeronumero exp = 1, kun taas max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Ohjainkoodi arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funktio Kutsu radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # Tämän koodin on antanut Mohit Kumra # Muokannut 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; } // Funktio, joka laskee eräänlaisen arr[] // exp:n edustaman numeron mukaan. function countSort(arr, exp) { const pituus = arr.length;  anna lähtö = Array(pituus); // tulostustaulukko anna count = Array(10).fill(0, 0);  // Tallenna esiintymien lukumäärä count[]:lle for (olkoon 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 numero = Math.floor(arr[i] / exp) % 10;  lähtö[luku[numero] - 1] = arr[i];  count[numero]--;  } palauttaa tulosteen; } // Pääfunktio, joka lajittelee arr[]-funktion käyttämällä kantaluku-lajittelufunktiota radixSort(arr) { // Etsi suurin määrä tiedossa olevien numeroiden lukumäärää const maxNumber = getMax(arr);  // Luo matala kopio, jossa lajitellut arvot säilytetään anna sortedArr = [...arr];  // Laske lajittelu jokaiselle numerolle. Huomaa, että // numeronumeron välittämisen sijaan välitetään exp.  // exp on 10^i, jossa i on nykyinen numeronumero kohteelle (olkoon exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Hanki Count lajitteluiteraatio const sortedIteration = countSort(sortedArr , exp);  sortedArr = lajiteltuIteraatio;  } return sortedArr; } /*Ohjainkoodi*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funktio Kutsu const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Tämän koodin tarjoaa 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--) { $tulos[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // Kopioi tuloste taulukkoon arr[], joten // tuo arr[] sisältää nyt lajiteltuja numeroita // nykyisen numeron mukaan ($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); } // Aputoiminto taulukkofunktion tulostamiseen 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 ?>>>Tikka2 24 45 66 75 90 170 802>

Radix-lajittelun monimutkaisuusanalyysi :

Aika monimutkaisuus:

• Kantalukulajittelu on ei-vertaileva kokonaislukulajittelualgoritmi, joka lajittelee tiedot kokonaislukuavaimilla ryhmittelemällä avaimet yksittäisten numeroiden mukaan, joilla on sama merkittävä sijainti ja arvo. Sillä on aika monimutkaisuus O(d * (n + b)) , jossa d on numeroiden lukumäärä, n on alkioiden lukumäärä ja b on käytetyn numerojärjestelmän kanta.
• Käytännön toteutuksissa kantalukulajittelu on usein nopeampi kuin muut vertailupohjaiset lajittelualgoritmit, kuten pikalajittelu tai yhdistämislajittelu, suurille tietojoukoille, varsinkin kun avaimissa on monta numeroa. Sen aika monimutkaisuus kuitenkin kasvaa lineaarisesti numeroiden määrän myötä, joten se ei ole yhtä tehokas pienille tietojoukoille.

Aputila:

• Radix-lajituksella on myös avaruuden monimutkaisuus O(n + b), missä n on alkioiden lukumäärä ja b on lukujärjestelmän kanta. Tämä tilan monimutkaisuus johtuu tarpeesta luoda kauhat jokaiselle numeroarvolle ja kopioida elementit takaisin alkuperäiseen taulukkoon jokaisen numeron lajittelun jälkeen.

Usein kysyttyjä kysymyksiä RadixSortista

Q1. Onko Radix Sort parempi kuin vertailupohjaiset lajittelualgoritmit, kuten Quick-Sort?

Jos meillä on loki₂n bittiä jokaista numeroa kohden, Radixin käyntiaika näyttää paremmalta kuin Quick Sort -toiminnon useilla syötenumeroilla. Asymptoottiseen merkintään piilotetut vakiotekijät ovat korkeammat Radix Sortissa ja Quick-Sort käyttää laitteistovälimuistia tehokkaammin. Myös Radix-lajittelu käyttää laskevaa lajittelua aliohjelmana ja laskentalajittelu vie ylimääräistä tilaa numeroiden lajitteluun.

bourne-ain -kuori

Q2. Entä jos elementit ovat vaihteluvälillä 1 - n ² ?

• Vertailupohjaisen lajittelualgoritmin (Yhdistäminen, Kekolajittelu, Quick-Sort jne.) alaraja on Ω(nLogn), eli ne eivät voi tehdä paremmin kuin nKirjaudu sisään . Laskentalajittelu on lineaarinen aikalajittelualgoritmi, joka lajittelee O(n+k) ajassa, kun elementit ovat alueella 1 - k.
• Emme voi käyttää laskevaa lajittelua, koska laskeva lajittelu kestää O(n²), mikä on huonompi kuin vertailupohjaiset lajittelualgoritmit. Voimmeko lajitella tällaisen taulukon lineaarisessa ajassa?
  • Lajittele Radix on vastaus. Radix-lajittelun ideana on lajitella numero kerrallaan vähiten merkitsevästä numerosta merkittävimpään numeroon. Radix-lajittelu käyttää laskentaa lajittelun aliohjelmana lajitteluun.