Radix Sort Algorithm in Data Structure

Co je Radix Sort Algorithm?

Radix Sort je nesrovnávací třídicí algoritmus. Funguje tak, že seskupuje jednotlivé číslice prvků, které mají být seřazeny. Stabilní technika třídění se pak používá k uspořádání prvků na základě jejich radixu. Jedná se o lineární třídicí algoritmus.

Proces třídění zahrnuje následující vlastnosti:

Nalezení maximálního prvku a získání počtu číslic tohoto prvku. Udává nám počet iterací, které bude proces řazení následovat.
Seskupte jednotlivé číslice prvků na stejné významné pozici v každé iteraci.
Proces seskupování začne od nejméně významné číslice a skončí na nejvyšší významné číslici.
Řazení prvků na základě číslic na této významné pozici.
Zachování relativního pořadí prvků, které mají stejnou hodnotu klíče. Tato vlastnost radix sort z něj dělá stabilní sortu.

Konečná iterace nám poskytne zcela seřazený seznam.

Fungování Radix Sort Algorithmu

Zkusme seřadit seznam celých čísel na výše uvedeném obrázku ve vzestupném pořadí pomocí algoritmu Radix Sort.

Zde jsou kroky k provedení procesu Radix Sorting:

Krok 1) Identifikujte prvek s maximální hodnotou v seznamu. V tomto případě je to 835.

Krok 2) Vypočítejte počet číslic maximálního prvku. 835 má přesně 3 číslice.

Krok 3) Určete počet iterací na základě kroku 2. 835 má 3 číslice, což znamená, že počet iterací bude 3.

Krok 4) Určete základnu prvků. Protože se jedná o desítkovou soustavu, základ bude 10.

Krok 5) Spusťte první iteraci.

a) První iterace

V první iteraci uvažujeme jednotkovou hodnotu každého prvku.

Krok 1) Upravte celé číslo o 10, abyste získali jednotkové místo prvků. Například 623 mod 10 nám dává hodnotu 3 a 248 mod 10 nám dává 8.

Krok 2) Použijte řazení počítání nebo jakékoli jiné stabilní řazení k uspořádání celých čísel podle jejich nejméně významné číslice. Jak je vidět z obrázku, 248 padne na 8. kbelík. 623 padne na 3. kbelík a tak dále.

Po první iteraci nyní seznam vypadá takto.

Jak můžete vidět z výše uvedeného obrázku, seznam ještě není seřazený a vyžaduje více iterací, aby byl plně seřazen.

b) Druhá iterace

V této iteraci budeme uvažovat číslici na 10^th místo pro proces třídění.

Krok 1) Vydělte celá čísla 10. 248 děleno 10 nám dává 24.

Krok 2) Upravte výstup z kroku 1 o 10. 24 mod 10 nám dává 4.

Krok 3) Postupujte podle kroku 2 z předchozí iterace.

Po druhé iteraci nyní seznam vypadá takto

Z výše uvedeného obrázku můžete vidět, že seznam stále není úplně seřazen, protože zatím není ve vzestupném pořadí.

c) Třetí iterace

Pro konečnou iteraci chceme získat nejvýznamnější číslici. V tomto případě je to 100^thmísto pro každé z celých čísel v seznamu.

Krok 1) Vydělte celá čísla 100… 415 děleno 100 nám dává 4.

Krok 2) Modifikujte výsledek z kroku 1 o 10. 4 mod 10 nám dává opět 4.

Krok 3) Postupujte podle kroku 3 z předchozí iterace.

Jak vidíme, seznam je nyní řazen vzestupně. Poslední iterace byla dokončena a proces řazení je nyní dokončen.

Pseudokód algoritmu řazení Radix

Zde je pseudokód pro Radix Sort Algorithm

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 pro implementaci 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);
}

Výstup:

162 248 415 623 835

Python Program pro Radix Sort Algorithm

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

Výstup:

[162,248,415,623,835]

Analýza složitosti Radix Sort

Je třeba zvážit dva typy složitosti, prostorovou složitost a časovou složitost.

Prostorová složitost: O(n+b) kde n je velikost pole a b je uvažovaná báze.
Časová složitost: O(d*(n+b)), kde d je počet číslic největšího prvku v poli.

Prostorová složitost Radix Sort

Dvě funkce, na které je třeba se zaměřit pro složitost prostoru

Počet prvků v poli, n.
Základ pro reprezentaci prvků, b.

Někdy může být tato základna větší než velikost pole.

Celková složitost je tedy O(n+b).

Následující vlastnosti prvků v seznamu mohou způsobit, že třídicí prostor radix bude neefektivní:

Prvky s velkým počtem číslic.
Základ prvků je velký, jako 64bitová čísla.

Časová složitost řazení Radix

Třídění počítání můžete použít jako podprogram, protože každá iterace bude trvate O(n+b) čas. Pokud existují d iterace, celková doba běhu se stane O(d*(n+b)). Zde „O“ znamená funkci složitosti.

Linearita Radix Sort

Radix Sort je lineární, když

d je konstantní, kde d je počet číslic největšího prvku.
b není ve velké míře větší ve srovnání s n.

Srovnání Radix Sort s jinými srovnávacími algoritmy

Jak jsme viděli, složitost řazení Radix je založena na velikosti slova nebo čísla. Bude to mít stejnou složitost pro průměrné a nejlepší případy. A to je O(d*(n+b)). Také se liší podle techniky třídění, kterou uprostřed používáte. Například můžete použít počítací třídění nebo rychlé třídění pro mezilehlý třídicí algoritmus uvnitř řazení Radix.

Aplikace Radix Sort Algorithmu

Důležité aplikace Radix Sort jsou:

Radix Sort lze použít jako algoritmus pro vyhledávání polohy, kde se používají velké rozsahy hodnot.
Používá se při konstrukci pole přípon v algoritmu DC3.
Používá se v sekvenčním stroji s náhodným přístupem přítomném v typickém počítači, kde jsou záznamy klíčovány.