Algoritmul de sortare Radix în structura datelor

Ce este algoritmul de sortare Radix?

Radix Sort este un algoritm de sortare necomparativ. Funcționează pe grupuriping cifrele individuale ale elementelor care urmează să fie sortate. Apoi se folosește o tehnică de sortare stabilă pentru a organiza elementele pe baza bazei 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. Aceasta oferă numărul de iterații pe care le efectuează procesul de sortare.
• Grouping cifrele individuale ale elementelor aflate la aceeași poziție semnificativă în fiecare iterație.
• Grupulping procesul începe de la cea mai puțin semnificativă cifră și se termină la cea mai semnificativă cifră.
• Sortarea elementelor în funcție de cifrele aflate în poziția semnificativă respectivă.
• Menținerea ordinii relative a elementelor care au aceeași valoare cheie. Această proprietate a sortării Radix Sort o face o sortare stabilă.

Iterația finală returnează o listă complet sortată.

Funcționarea algoritmului de sortare Radix

Lista numerelor întregi de sortat

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

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

Pas 1) Identificați elementul maxim din listă. Aici este 835.

Pas 2) Numără-i cifrele. 835 are 3 cifre, deci numărul de iterații este 3.

Pas 3) Determinați baza. Deoarece este un număr zecimal, baza este 10.

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

a) Prima iterație

Sortare după ultima cifră

Î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 poziția unității elementelor. De exemplu, 623 mod 10 dă 3, iar 248 mod 10 dă 8.

Pas 2) Folosește sortarea numerică sau o altă sortare stabilă pentru a organiza numerele întregi în funcție de cea mai mică cifră semnificativă. Din figură, 248 se încadrează în a 8-a categorie, 623 se încadrează în a 3-a categorie și așa mai departe.

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

Lista după prima iterație

Lista nu este încă sortată și necesită mai multe iterații.

b) A doua iterație

Sortare pe baza cifrelor de la locul zecilor

În această iterație, considerăm cifra din locul zecilor pentru procesul de sortare.

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

Pas 2) Modulați rezultatul Pasului 1 cu 10. 24 modul 10 dă 4.

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

După a doua iterație, lista arată acum astfel:

Listează după a doua iterație

Lista nu este încă sortată complet, deoarece nu este încă în ordine crescătoare.

c) A treia iterație

Sortarea în funcție de cifrele de pe locul sutelor

Pentru iterația finală, dorim să obținem cea mai semnificativă cifră. În acest caz, este vorba de cifra sutelor pentru fiecare număr întreg din listă.

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

Pas 2) Modulați rezultatul de la Pasul 1 cu 10. 4 modulând 10 obțineți 4.

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

Lista după a treia iterație

Lista este acum sortată în ordine crescătoare. Iterația finală a fost finalizată, iar procesul de sortare este finalizat.

Pseudocod al algoritmului de sortare Radix

Iată pseudocodul 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 jth 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 in the jth place
    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 integer
    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 in 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

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

ieșire:

[162, 248, 415, 623, 835]

Analiza complexității sortării pe bază de radix

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

• Complexitatea spațiului: O(n + b) unde n este dimensiunea tabloului și b este baza considerată.
• Complexitatea timpului: O(d * (n + b)) unde d este numărul de cifre al celui mai mare element din matrice.

Complexitatea spațială a sortării Radix

Două caracteristici pe care să ne concentrăm pentru complexitatea spațiului:

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

Uneori, această bază poate fi mai mare decât dimensiunea tabloului. Complexitatea totală este, așadar, 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

Folosind sortarea prin numărare ca subrutină, fiecare iterație are loc O(n + b) timp. Dacă există d iterații, timpul total de rulare devine O(d * (n + b))Aici, „O” reprezintă funcția de complexitate.

Linearitatea sortării Radix

Sortarea la bază este liniară când:

• d este constantă, unde d este numărul de cifre ale celui mai mare element.
• b nu este semnificativ mai mare decât n.

Compararea sortării bazate pe radix cu alte tipuri de sortare Algorithms

Complexitatea sortării Radix depinde de dimensiunea numărului. Atât cazul optim, cât și cazul mediu sunt O(d * (n + b)). Performanța variază în funcție de sortarea internă — sortarea numerică este standard, dar orice sortare stabilă funcționează.

Aplicații ale algoritmului de sortare Radix

Aplicațiile importante ale sortării Radix sunt:

• Radix Sort poate fi utilizat ca algoritm de găsire a locației acolo unde sunt implicate intervale mari de valori.
• Este folosit pentru a construi o matrice de sufixe în algoritmul DC3.
• Se utilizează în mașini secvențiale, cu acces aleatoriu, unde înregistrările sunt cheiate prin identificatori cu lățime fixă.

Întrebări frecvente