// 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];  grįžti mx; } // Funkcija, skirta atlikti skaičiavimo rūšį arr[] // pagal skaitmenį //, pavaizduotą exp. void countSort(int arr[], int n, int exp) { // Išvesties masyvas int output[n];  int i, skaičius[10] = {0};  // Išsaugoti įvykių skaičių // skaičiuje[], kai (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--) { išvestis[skaičiuoti[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Nukopijuokite išvesties masyvą į arr[], // kad arr[] dabar būtų surūšiuoti // skaičiai pagal esamą skaitmenį (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); } // Naudingumo funkcija masyvo spausdinimui 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];  grįžti mx;  } // Funkcija, skirta skaičiuoti arr[] pagal // skaitmenį, pavaizduotą exp.  statinis void skaičius Rūšiuoti(int arr[], int n, int exp) { int output[] = new int[n]; // išvesties masyvas int i;  int count[] = naujas int[10];  Masyvai.užpildyti(skaičius, 0);  // Išsaugoti įvykių skaičių count[], kai (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--) { išvestis[skaičiuoti[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Nukopijuokite išvesties masyvą į arr[], kad arr[] dabar // būtų surūšiuoti skaičiai pagal esamą // skaitmenį (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);  } // Naudingumo funkcija spausdinti masyvo statinį 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: indeksas = arr[i] // exp1 output[count[index % 10] - 1] = arr[i] count[indeksas % 10] -= 1 i -= 1 # Išvesties masyvo kopijavimas į arr[] , # kad arr dabar būtų surūšiuoti skaičiai i = 0 diapazone(0, len(arr)): arr[i] = output[i] # Būdas, kaip atlikti Radix Rūšiuoti def radixSort(arr): # Raskite maksimalų skaičius, norint sužinoti skaitmenų skaičių max1 = max(arr) # Atlikite kiekvieno skaitmens skaičiavimo rūšiavimą. Atminkite, kad vietoj # perduodamas skaitmuo, perduodamas exp. exp yra 10^i #, kur i yra dabartinis skaitmenų skaičius exp = 1, o max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Tvarkyklės kodas arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funkcija Iškviesti radixSort(arr) for i diapazone(len(arr)): print(arr[i], end=' ') # Šį kodą sukūrė Mohit Kumra # Redagavo 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; } // Funkcija, skirta skaičiuoti arr[] pagal // skaitmenį, pavaizduotą exp. function countSort(arr, exp) { const ilgis = arr.length;  tegul išvestis = Masyvas(ilgis); // išvesties masyvas let count = Array(10).fill(0, 0);  // Išsaugoti įvykių skaičių count[] for (tegul 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 skaitmuo = Math.floor(arr[i] / exp) % 10;  išvestis[skaičius[skaitmuo] - 1] = arr[i];  skaičius [skaitmuo]--;  } grąžinti išvestį; } // Pagrindinė funkcija, kuri rūšiuoja arr[] naudojant radikso rūšiavimo funkciją radixSort(arr) { // Raskite maksimalų skaičių, kurį reikia žinoti skaitmenų skaičių const maxNumber = getMax(arr);  // Sukurkite seklią kopiją, kurioje bus saugomos surūšiuotos reikšmės, tegul sortedArr = [...arr];  // Atlikite kiekvieno skaitmens skaičiavimo rūšiavimą. Atminkite, kad // vietoj skaitmens skaičiaus perduodamas exp.  // exp yra 10^i, kur i yra dabartinis skaitmenų skaičius (tegul exp = 1; Math.floor(maks.Skaičius / exp)> 0; exp *= 10) { // Gauti Count rūšiavimo iteraciją const sortedIteration = countSort(sortedArr , exp);  sortedArr = sortedIteration;  } return sortedArr; } /*Vairuotojo kodas*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funkcija Call const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Šį kodą sukūrė beeduhboodee>>PHP>>Smiginis2 24 45 66 75 90 170 802>

Radix Sort sudėtingumo analizė :

Laiko sudėtingumas:

• Radix sort yra nelyginamasis sveikųjų skaičių rūšiavimo algoritmas, kuris rūšiuoja duomenis sveikųjų skaičių raktais, sugrupuodamas raktus pagal atskirus skaitmenis, kurie turi tą pačią reikšmingą vietą ir reikšmę. Jis turi laiko sudėtingumą O(d * (n + b)) , kur d yra skaitmenų skaičius, n yra elementų skaičius, o b yra naudojamos skaičių sistemos pagrindas.
• Praktikoje rūšiavimas radiksu dažnai yra greitesnis nei kiti palyginimu pagrįsti rūšiavimo algoritmai, tokie kaip greitasis rūšiavimas arba suliejimo rūšiavimas, kai naudojami dideli duomenų rinkiniai, ypač kai raktai turi daug skaitmenų. Tačiau jo sudėtingumas laike didėja tiesiškai didėjant skaitmenų skaičiui, todėl jis nėra toks efektyvus mažiems duomenų rinkiniams.

Pagalbinė erdvė:

• Radix rūšiavimas taip pat turi erdvės sudėtingumą O(n + b), kur n yra elementų skaičius, o b yra skaičių sistemos pagrindas. Šis erdvės sudėtingumas atsiranda dėl poreikio sukurti segmentus kiekvienai skaitmens vertei ir nukopijuoti elementus atgal į pradinį masyvą, kai kiekvienas skaitmuo buvo surūšiuotas.

Dažnai užduodami klausimai apie RadixSort

Q1. Ar „Radix Sort“ yra geresnis už palyginimu pagrįstus rūšiavimo algoritmus, tokius kaip „Quick-Sort“?

Jei turime žurnalą₂n bitų kiekvienam skaitmeniui, Radix veikimo laikas yra geresnis nei greitojo rūšiavimo, kai naudojamas platus įvesties skaičių diapazonas. Pastovūs veiksniai, paslėpti asimptotiniame žymėjime, yra didesni Radix Sort ir Quick-Sort efektyviau naudoja aparatinės įrangos talpyklas. Be to, Radix sort naudoja skaičiavimo rūšiavimą kaip paprogramę, o skaičiavimo rūšiavimas užima papildomos vietos skaičiams rūšiuoti.

operacinės sistemos naudojimas

Q2. Ką daryti, jei elementai yra svyruoja nuo 1 iki n ² ?

• Palyginimu pagrįsto rūšiavimo algoritmo apatinė riba (sujungimo rūšiavimas, krūvos rūšiavimas, greitas rūšiavimas .. ir tt) yra Ω (nLogn), t. y. jie negali veikti geriau nei nPrisijungti . Skaičiavimo rūšiavimas yra linijinis laiko rūšiavimo algoritmas, kuris rūšiuoja pagal O(n+k) laiką, kai elementai yra intervale nuo 1 iki k.
• Negalime naudoti skaičiavimo rūšiavimo, nes skaičiavimo rūšiavimas užtruks O (n²), kuris yra blogesnis už palyginimu pagrįstus rūšiavimo algoritmus. Ar galime rūšiuoti tokį masyvą tiesiniu laiku?
  • Rūšiuoti Radix yra atsakymas. Radix Sort idėja yra rūšiuoti po skaitmenis, pradedant nuo mažiausiai reikšmingo skaitmens iki reikšmingiausio skaitmens. Radix sort naudoja skaičiavimo rūšiavimą kaip rūšiavimo paprogramę.