Radix rendezési algoritmus az adatstruktúrában

Mi az a Radix rendezési algoritmus?

A Radix Sort egy nem összehasonlító rendezési algoritmus. Úgy működik, hogy csoportosítja a rendezendő elemek egyes számjegyeit. Ezután egy stabil rendezési technikát alkalmaznak az elemek gyökük szerinti rendszerezésére. Ez egy lineáris rendezési algoritmus.

A válogatási folyamat a következő tulajdonságokat tartalmazza:

A maximális elem megkeresése és az adott elem számjegyeinek megszerzése. Megadja az iterációk számát a rendezési folyamat során.
Csoportosítsa az elemek egyes számjegyeit minden iterációban ugyanazon a jelentős helyen.
A csoportosítási folyamat a legkisebb jelentőségű számjegytől kezdődik, és a legjelentősebb számjegynél ér véget.
Az elemek rendezése számjegyek alapján az adott jelentős helyen.
Az azonos kulcsértékkel rendelkező elemek relatív sorrendjének fenntartása. A radix rendezés ezen tulajdonsága stabil rendezést biztosít.

Az utolsó iteráció egy teljesen rendezett listát ad nekünk.

A Radix rendezési algoritmus működése

Próbáljuk meg a fenti ábrán látható egész számok listáját a Radix Sort algoritmussal növekvő sorrendbe rendezni.

Íme a Radix rendezési folyamat lépései:

Step 1) Azonosítsa a listában a maximális értékű elemet. Ebben az esetben a 835.

Step 2) Számítsa ki a maximális elem számjegyeinek számát! A 835 pontosan 3 számjegyből áll.

Step 3) Határozza meg az iterációk számát a 2. lépés alapján. A 835 3 számjegyű, vagyis az iterációk száma 3 lesz.

Step 4) Határozza meg az elemek alapját! Mivel ez egy tizedes rendszer, az alap 10 lesz.

Step 5) Indítsa el az első iterációt.

a) Első iteráció

Az első iterációban az egyes elemek egységnyi helyiértékét vesszük figyelembe.

Step 1) Módosítsa az egész számot 10-zel, hogy megkapja az elemek egységhelyét. Például a 623 mod 10 értéke 3, a 248 mod 10 pedig 8.

Step 2) Használja a számláló rendezést vagy bármilyen más stabil rendezést az egész számok legkisebb jelentőségű számjegyük szerinti rendezéséhez. Amint az ábrán látható, a 248 a 8. vödörre esik. A 623 a 3. vödörre fog esni és így tovább.

Az első iteráció után a lista most így néz ki.

Amint az a fenti ábrán látható, a lista még nincs rendezve, és további iterációt igényel a teljes rendezéshez.

b) Második iteráció

Ebben az iterációban a 10-es számjegyet fogjuk figyelembe venni^th hely a válogatási folyamathoz.

Step 1) Osszuk el az egész számokat 10-zel. 248 osztva 10-zel 24-et kapunk.

Step 2) Módosítsa az 1. lépés kimenetét 10-re. 24 A 10. mod 4-et ad.

Step 3) Kövesse az előző iteráció 2. lépését.

A második iteráció után a lista most így néz ki

A fenti ábrán látható, hogy a lista még mindig nincs teljesen rendezve, mivel még nincs növekvő sorrendben.

c) Harmadik iteráció

Az utolsó iterációhoz a legjelentősebb számjegyet szeretnénk megkapni. Ebben az esetben ez a 100^thhelyet a listában szereplő összes egész számhoz.

Step 1) Osszuk el az egész számokat 100-zal… 415 osztva 100-zal 4-et kapunk.

Step 2) Módosítsa az 1. lépés eredményét 10-re. 4 A mod 10 ismét 4-et ad.

Step 3) Kövesse az előző iteráció 3. lépését.

Amint látjuk, a lista most növekvő sorrendben van rendezve. Az utolsó iteráció befejeződött, és a rendezési folyamat befejeződött.

Radix rendezési algoritmus pszeudokódja

Itt van a Radix Sort Algorithm pszeudokódja

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 a Radix Sort megvalósításához

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

output:

162 248 415 623 835

Python Program a Radix rendezési algoritmushoz

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

output:

[162,248,415,623,835]

A Radix Sort komplexitáselemzése

A komplexitásnak két típusát kell figyelembe venni, a térbeli és az időbeli összetettséget.

Térkomplexitás: O(n+b) ahol n a tömb mérete, b pedig a figyelembe vett bázis.
Időbonyolultság: O(d*(n+b)), ahol d a tömb legnagyobb elemének számjegyeinek száma.

A Radix rendezés térkomplexitása

Két olyan funkció, amelyre összpontosítani kell a tér összetettsége érdekében

A tömb elemeinek száma, n.
Az elemek ábrázolásának alapja, b.

Néha ez az alap nagyobb lehet, mint a tömb mérete.

A teljes komplexitás tehát O(n+b).

A lista elemeinek következő tulajdonságai miatt a radix rendezési terület nem hatékony:

Sok számjegyű elemek.
Az elemek alapja nagy, mint a 64 bites számok.

A Radix rendezés időbeli összetettsége

A számláló rendezést használhatja szubrutinként, mivel minden iteráció megtörténike O(n+b) idő. Ha d iteráció létezik, a teljes futási idő a következő lesz O(d*(n+b)). Itt az „O” a komplexitási függvényt jelenti.

Radix rendezés linearitása

A Radix Sort lineáris, amikor

d állandó, ahol d a legnagyobb elem számjegyeinek száma.
b nem nagy mértékben nagyobb ahhoz képest n.

A Radix Sort összehasonlítása más összehasonlító algoritmusokkal

Amint láttuk, a Radix rendezés összetettsége egy szó vagy szám méretén alapul. Ugyanolyan összetett lesz az átlagos és a legjobb esetekben. Ez pedig O(d*(n+b)). Ezenkívül eltér a középen használt válogatási technikától függően. Például használhatja a számláló rendezést vagy a gyors rendezést a köztes rendezési algoritmushoz a Radix rendezésen belül.

Radix Sort Algorithm alkalmazásai

A Radix Sort fontos alkalmazásai a következők:

A Radix Sort helymeghatározó algoritmusként használható, ahol nagy értéktartományokat használnak.
A DC3 algoritmusban egy utótag tömb felépítésére használják.
Egy szekvenciális, véletlen hozzáférésű gépben használatos, amely egy tipikus számítógépben található, ahol a rekordokat kulcsolják.