Radix algoritam sortiranja u strukturi podataka

Što je Radix algoritam sortiranja?

Radix Sort je neusporedni algoritam sortiranja. Djeluje tako da grupira pojedinačne znamenke elemenata koje treba sortirati. Zatim se koristi stabilna tehnika sortiranja za organiziranje elemenata na temelju njihovog radiksa. To je linearni algoritam sortiranja.

Proces sortiranja uključuje sljedeća svojstva:

  • Pronalaženje maksimalnog elementa i dobivanje broja znamenki tog elementa. Daje nam broj ponavljanja koje će proces sortiranja slijediti.
  • Grupirajte pojedinačne znamenke elemenata na istoj značajnoj poziciji u svakoj iteraciji.
  • Proces grupiranja započet će od najmanje značajne znamenke i završiti na najznačajnijoj znamenki.
  • Razvrstavanje elemenata na temelju znamenki na toj značajnoj poziciji.
  • Održavanje relativnog poretka elemenata koji imaju istu ključnu vrijednost. Ovo svojstvo radikalne sorte čini je stabilnom sortom.

Konačna iteracija će nam dati potpuno sortirani popis.

Rad algoritma radix sortiranja

Rad algoritma radix sortiranja
Popis cijelih brojeva koje treba sortirati

Pokušajmo sortirati popis cijelih brojeva na gornjoj slici uzlaznim redoslijedom pomoću algoritma Radix Sort.

Evo koraka za izvođenje postupka radix sortiranja:

Korak 1) Identificirajte element s najvećom vrijednošću na popisu. U ovom slučaju to je 835.

Korak 2) Izračunajte broj znamenki maksimalnog elementa. 835 ima točno 3 znamenke.

Korak 3) Odredite broj ponavljanja na temelju koraka 2. 835 ima 3 znamenke, što znači da će broj ponavljanja biti 3.

Korak 4) Odredite bazu elemenata. Budući da je ovo decimalni sustav, baza će biti 10.

Korak 5) Započnite prvu iteraciju.

a) Prva iteracija

Rad algoritma radix sortiranja
Sortiranje po zadnjoj znamenki

U prvoj iteraciji razmatramo jediničnu vrijednost svakog elementa.

Korak 1) Modificirajte cijeli broj za 10 da dobijete mjesto jedinice elemenata. Na primjer, 623 mod 10 daje nam vrijednost 3, a 248 mod 10 daje nam 8.

Korak 2) Upotrijebite sortiranje brojanjem ili bilo koje drugo stabilno sortiranje da organizirate cijele brojeve prema njihovoj najmanje značajnoj znamenki. Kao što se vidi sa slike, 248 će pasti na 8. kantu. 623 će pasti na 3. kantu i tako dalje.

Nakon prve iteracije lista sada izgleda ovako.

Rad algoritma radix sortiranja
Popis nakon prve iteracije

Kao što možete vidjeti na gornjoj slici, popis još nije sortiran i zahtijeva više ponavljanja da bi bio u potpunosti sortiran.

b) Druga iteracija

Rad algoritma radix sortiranja
Sortiranje na temelju znamenki na mjestu desetica

U ovoj iteraciji, razmotrit ćemo znamenku na 10th mjesto za proces sortiranja.

Korak 1) Podijelite cijele brojeve s 10. 248 podijeljeno s 10 daje nam 24.

Korak 2) Izmijenite izlaz koraka 1 za 10. 24 mod 10 daje nam 4.

Korak 3) Slijedite korak 2 iz prethodne iteracije.

Nakon druge iteracije lista sada izgleda ovako

Rad algoritma radix sortiranja
Popis nakon druge iteracije

Na gornjoj slici možete vidjeti da lista još uvijek nije u potpunosti sortirana jer još nije u uzlaznom redoslijedu.

c) Treća iteracija

Rad algoritma radix sortiranja
Sortiranje na temelju znamenki na stotinama mjesta

Za posljednju iteraciju, želimo dobiti najznačajniju znamenku. U ovom slučaju, to je 100th mjesto za svaki od cijelih brojeva na listi.

Korak 1) Podijelite cijele brojeve sa 100... 415 podijeljeno sa 100 daje nam 4.

Korak 2) Modificirajte rezultat iz koraka 1 za 10. 4 mod 10 opet nam daje 4.

Korak 3) Slijedite korak 3 iz prethodne iteracije.

Rad algoritma radix sortiranja
Popis nakon trećeg ponavljanja

Kao što vidimo, lista je sada poredana uzlaznim redoslijedom. Završna iteracija je završena i proces sortiranja je sada završen.

Pseudokod Radix algoritma sortiranja

Ovdje je pseudokod za Radix algoritam sortiranja

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 of the elements in the jthplace
   arr = sorted elements

C++ Program za implementaciju Radix sortiranja

#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);
}

Izlaz:

162 248 415 623 835

Python Program za Radix algoritam sortiranja

#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)

Izlaz:

[162,248,415,623,835]

Analiza složenosti Radix sortiranja

Postoje dvije vrste složenosti koje treba razmotriti, prostorna složenost i vremenska složenost.

  • Složenost prostora: O(n+b) gdje je n veličina niza, a b je baza koja se razmatra.
  • Vremenska složenost: O(d*(n+b)) gdje je d broj znamenki najvećeg elementa u nizu.

Prostorna složenost radix sortiranja

Dvije značajke na koje se treba usredotočiti za složenost prostora

  • Broj elemenata u nizu, n.
  • Osnova za predstavljanje elemenata, b.

Ponekad ta baza može biti veća od veličine niza.

Ukupna složenost je stoga O(n+b).

Sljedeća svojstva elemenata na popisu mogu učiniti prostor radix sortiranja neučinkovitim:

  • Elementi s velikim brojem znamenki.
  • Baza elemenata je velika, poput 64-bitnih brojeva.

Vremenska složenost radix sortiranja

Možete koristiti sortiranje brojanjem kao potprogram, jer će svaka iteracija trajatie O(n+b) vrijeme. Ako postoje iteracije, ukupno vrijeme rada postaje O(d*(n+b)). Ovdje "O" označava funkciju složenosti.

Linearnost radix sortiranja

Radix sortiranje je linearno kada

  • d je konstanta, gdje je d broj znamenki najvećeg elementa.
  • b nije veći u velikoj mjeri u usporedbi s n.

Usporedbe Radix Sort-a s drugim usporednim algoritmima

Kao što smo vidjeli, složenost Radix sortiranja temelji se na veličini riječi ili broja. Bit će iste složenosti za prosječne i najbolje slučajeve. A to je O(d*(n+b)). Također, razlikuje se prema tehnici sortiranja koju koristite u sredini. Na primjer, možete koristiti sortiranje brojanjem ili brzo sortiranje za srednji algoritam sortiranja unutar Radix sortiranja.

Primjene Radix algoritma sortiranja

Važne primjene Radix sortiranja su:

  • Radix sortiranje može se koristiti kao algoritam za pronalaženje lokacije gdje se koriste veliki rasponi vrijednosti.
  • Koristi se za konstruiranje niza sufiksa u DC3 algoritmu.
  • Koristi se u sekvencijalnom stroju s nasumičnim pristupom koji je prisutan u tipičnom računalu gdje se zapisi unose ključem.