Algoritmul de sortare Radix în structura datelor

Ce este algoritmul de sortare Radix?

Radix Sort este un algoritm de sortare non-comparativ. Funcționează prin gruparea cifrelor individuale ale elementelor de sortat. O tehnică de sortare stabilă este apoi utilizată pentru a organiza elementele pe baza rădăcinii lor. Este un algoritm de sortare liniară.

Procesul de sortare implică următoarele proprietăți:

Găsirea elementului maxim și obținerea numărului de cifre ale acelui element. Ne oferă numărul de iterații pe care le va urma procesul de sortare.
Grupați cifrele individuale ale elementelor în aceeași poziție semnificativă în fiecare iterație.
Procesul de grupare va începe de la cifra cea mai puțin semnificativă și se va termina cu cifra cea mai semnificativă.
Sortarea elementelor pe baza cifrelor din acea poziție semnificativă.
Menținerea ordinii relative a elementelor care au aceeași valoare a cheii. Această proprietate a sortării radix îl face un sortare stabil.

Iterația finală ne va oferi o listă complet sortată.

Funcționarea algoritmului de sortare Radix

Să încercăm să sortăm lista de numere întregi din figura de mai sus în ordine crescătoare folosind algoritmul Radix Sort.

Iată pașii pentru a efectua procesul de sortare Radix:

Pas 1) Identificați elementul cu valoarea maximă din listă. În acest caz, este 835.

Pas 2) Calculați numărul de cifre ale elementului maxim. 835 are exact 3 cifre.

Pas 3) Determinați numărul de iterații pe baza pasului 2. 835 are 3 cifre, ceea ce înseamnă că numărul de iterații va fi 3.

Pas 4) Determinați baza elementelor. Deoarece acesta este un sistem zecimal, baza va fi 10.

Pas 5) Începeți prima iterație.

a) Prima iterație

În prima iterație, luăm în considerare valoarea locului unitară a fiecărui element.

Pas 1) Modificați numărul întreg cu 10 pentru a obține locul unitar al elementelor. De exemplu, 623 mod 10 ne dă valoarea 3, iar 248 mod 10 ne dă 8.

Pas 2) Utilizați sortarea de numărare sau orice altă sortare stabilă pentru a organiza numerele întregi în funcție de cifra lor cea mai puțin semnificativă. După cum se vede din figură, 248 va cădea pe a 8-a găleată. 623 va cădea pe a 3-a găleată și așa mai departe.

După prima iterație, lista arată acum așa.

După cum puteți vedea din figura de mai sus, lista nu este încă sortată și necesită mai multe iterații pentru a fi sortată complet.

b) A doua iterație

În această iterație, vom lua în considerare cifra de la 10^th loc pentru procesul de sortare.

Pas 1) Împărțiți numerele întregi la 10. 248 împărțit la 10 ne dă 24.

Pas 2) Modificați rezultatul pasului 1 cu 10. 24 mod 10 ne oferă 4.

Pas 3) Urmați pasul 2 din iterația anterioară.

După a doua iterație, lista arată acum așa

Puteți vedea din figura de mai sus că lista încă nu este sortată complet, deoarece nu este încă în ordine crescătoare.

c) A treia iterație

Pentru ultima iterație, dorim să obținem cea mai semnificativă cifră. În acest caz, este 100^thloc pentru fiecare dintre numerele întregi din listă.

Pas 1) Împărțiți numerele întregi la 100... 415 împărțit la 100 ne dă 4.

Pas 2) Modificați rezultatul de la pasul 1 cu 10. 4 mod 10 ne dă din nou 4.

Pas 3) Urmați pasul 3 din iterația anterioară.

După cum putem vedea, lista este sortată acum în ordine crescătoare. Iterația finală a fost finalizată, iar procesul de sortare este acum încheiat.

Pseudocod al algoritmului de sortare Radix

Iată pseudo-codul pentru algoritmul de sortare Radix

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Program pentru implementarea Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

ieșire:

162 248 415 623 835

Python Program pentru algoritmul de sortare Radix

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

ieșire:

[162,248,415,623,835]

Analiza complexității Radix Sort

Există două tipuri de complexitate de luat în considerare, complexitatea spațială și complexitatea timpului.

Complexitatea spațiului: O(n+b) unde n este dimensiunea matricei și b este baza luată în considerare.
Complexitatea timpului: O(d*(n+b)) unde d este numărul de cifre ale celui mai mare element din matrice.

Complexitatea spațială a sortării Radix

Două caracteristici pe care să vă concentrați pentru complexitatea spațiului

Numărul de elemente din matrice, n.
Baza pentru reprezentarea elementelor, b.

Uneori, această bază poate fi mai mare decât dimensiunea matricei.

Complexitatea globală este astfel O(n+b).

Următoarele proprietăți ale elementelor din listă pot face ca spațiul de sortare radix să fie ineficient:

Elemente cu un număr mare de cifre.
Baza elementelor este mare, precum numerele pe 64 de biți.

Complexitatea temporală a sortării Radix

Puteți utiliza sortarea de numărare ca subrutină, deoarece fiecare iterație va durae O(n+b) timp. Dacă există d iterații, timpul total de rulare devine O(d*(n+b)). Aici, „O” înseamnă funcția de complexitate.

Linearitatea sortării Radix

Sortarea Radix este liniară când

d este constantă, unde d este numărul de cifre ale celui mai mare element.
b nu este mai mare în mare măsură în comparație cu n.

Comparații dintre Radix Sort cu alți algoritmi comparativi

După cum am văzut, complexitatea sortării Radix se bazează pe dimensiunea unui cuvânt sau a unui număr. Va avea aceeași complexitate pentru cazurile medii și cele mai bune. Și acesta este O(d*(n+b)). De asemenea, diferă în funcție de tehnica de sortare pe care o folosești la mijloc. De exemplu, puteți utiliza sortarea prin numărare sau sortarea rapidă pentru algoritmul de sortare intermediar din cadrul sortării Radix.

Aplicații ale algoritmului de sortare Radix

Aplicațiile importante ale Radix Sort sunt:

Radix Sort poate fi folosit ca algoritm de găsire a locației în cazul în care sunt utilizate intervale mari de valori.
Este folosit la construirea unui tablou de sufixe în algoritmul DC3.
Este utilizat într-o mașină secvenţială, cu acces aleatoriu, prezentă într-un computer tipic în care înregistrările sunt tastate.

S-ar putea sa-ti placa: