Radix-sorteringsalgoritme i datastruktur

Hvad er Radix Sort Algorithm?

Radix Sort er en ikke-komparativ sorteringsalgoritme. Det fungerer ved at gruppere de individuelle cifre i de elementer, der skal sorteres. En stabil sorteringsteknik bruges derefter til at organisere elementerne ud fra deres radix. Det er en lineær sorteringsalgoritme.

Sorteringsprocessen involverer følgende egenskaber:

At finde det maksimale element og indhente antallet af cifre i det element. Det giver os antallet af iterationer, sorteringsprocessen vil følge.
Gruppér de individuelle cifre i elementerne på den samme signifikante position i hver iteration.
Grupperingsprocessen starter fra det mindst signifikante ciffer og slutter ved det mest signifikante ciffer.
Sortering af elementerne baseret på cifre på den signifikante position.
Opretholdelse af den relative rækkefølge af elementer, der har samme nøgleværdi. Denne egenskab af radix-sorten gør det til en stabil sort.

Den endelige iteration vil give os en fuldstændig sorteret liste.

Arbejde med Radix Sort Algorithm

Lad os prøve at sortere listen over heltal i ovenstående figur i stigende rækkefølge ved hjælp af Radix Sort-algoritmen.

Her er trinene til at udføre Radix-sorteringsprocessen:

Trin 1) Identificer elementet med den maksimale værdi på listen. I dette tilfælde er det 835.

Trin 2) Beregn antallet af cifre i det maksimale element. 835 har 3 cifre nøjagtigt.

Trin 3) Bestem antallet af iterationer baseret på trin 2. 835 har 3 cifre, hvilket betyder, at antallet af iterationer vil være 3.

Trin 4) Bestem grunden af elementerne. Da dette er et decimalsystem, vil grundtallet være 10.

Trin 5) Start den første iteration.

a) Første iteration

I den første iteration betragter vi enhedspladsværdien for hvert element.

Trin 1) Ændr hele tallet med 10 for at få enhedspladsen for elementerne. For eksempel giver 623 mod 10 os værdien 3, og 248 mod 10 giver os 8.

Trin 2) Brug tællesortering eller en hvilken som helst anden stabil sortering til at organisere de heltal i overensstemmelse med deres mindst signifikante ciffer. Som det ses af figuren vil 248 falde på den 8. spand. 623 vil falde på den 3. spand og så videre.

Efter den første iteration ser listen nu sådan ud.

Som du kan se fra ovenstående figur, er listen ikke sorteret endnu og kræver mere iteration for at være fuldt sorteret.

b) Anden iteration

I denne iteration vil vi overveje tallet ved 10^th sted for sorteringsprocessen.

Trin 1) Divider de heltal med 10. 248 divideret med 10 giver os 24.

Trin 2) Mod output fra trin 1 med 10. 24 mod 10 giver os 4.

Trin 3) Følg trin 2 fra den forrige iteration.

Efter den anden iteration ser listen nu sådan ud

Du kan se fra ovenstående figur, at listen stadig ikke er helt sorteret, da den ikke er i stigende rækkefølge endnu.

c) Tredje iteration

Til den endelige iteration ønsker vi at få det mest signifikante ciffer. I dette tilfælde er det 100^thplads for hvert af de heltal på listen.

Trin 1) Divider hele tallene med 100... 415 divideret med 100 giver os 4.

Trin 2) Mod resultatet fra trin 1 med 10. 4 mod 10 giver os 4 igen.

Trin 3) Følg trin 3 fra den forrige iteration.

Som vi kan se, er listen nu sorteret i stigende rækkefølge. Den endelige iteration er afsluttet, og sorteringsprocessen er nu afsluttet.

Pseudokode for Radix Sort Algorithm

Her er pseudokoden for 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 til implementering af 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);
}

Output:

162 248 415 623 835

Python Program til 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)

Output:

[162,248,415,623,835]

Kompleksitetsanalyse af Radix Sort

Der er to typer kompleksitet at overveje, rumkompleksitet og tidskompleksitet.

Rumkompleksitet: O(n+b), hvor n er størrelsen af arrayet, og b er den betragtede base.
Tidskompleksitet: O(d*(n+b)) hvor d er antallet af cifre i det største element i arrayet.

Rumkompleksiteten af Radix Sort

To funktioner at fokusere på for rummets kompleksitet

Antal elementer i arrayet, n.
Grundlaget for at repræsentere elementerne, b.

Nogle gange kan denne base være større end størrelsen af arrayet.

Den overordnede kompleksitet er således O(n+b).

Følgende egenskaber for elementerne på listen kan gøre radix-sorteringspladsen ineffektiv:

Elementer med et stort antal cifre.
Basen af elementerne er stor, ligesom 64-bit tal.

Tidskompleksitet af Radix Sort

Du kan bruge tællesorten som en underrutine, da hver iteration vil tagee O(n+b) tid. Hvis der findes d iterationer, bliver den samlede køretid O(d*(n+b)). Her betyder "O" kompleksitetsfunktionen.

Linearitet af Radix Sort

Radix Sort er lineær hvornår

d er konstant, hvor d er antallet af cifre i det største grundstof.
b er ikke større i særlig grad i forhold til n.

Sammenligninger af Radix Sort med andre komparative algoritmer

Som vi har set, er Radix-sortens kompleksitet baseret på en ord- eller talstørrelse. Det vil have samme kompleksitet for de gennemsnitlige og bedste sager. Og det er O(d*(n+b)). Det er også forskelligt alt efter den sorteringsteknik, du bruger i midten. For eksempel kan du bruge tællesortering eller hurtig sortering til den mellemliggende sorteringsalgoritme inde i Radix-sorteringen.

Anvendelser af Radix Sort Algorithm

Vigtige anvendelser af Radix Sort er:

Radix Sort kan bruges som en lokationsfindingsalgoritme, hvor der bruges store værdiområder.
Det bruges til at konstruere et suffiksarray i DC3-algoritmen.
Det bruges i en sekventiel, tilfældig adgangsmaskine, der er til stede i en typisk computer, hvor optegnelser indtastes.

Du kan lide: