Radix sorteringsalgoritme i datastruktur

Hva er Radix Sort Algorithm?

Radix Sort er en ikke-komparativ sorteringsalgoritme. Det fungerer ved å gruppere de individuelle sifrene til elementene som skal sorteres. En stabil sorteringsteknikk brukes deretter for å organisere elementene basert på deres radix. Det er en lineær sorteringsalgoritme.

Sorteringsprosessen involverer følgende egenskaper:

• Finne det maksimale elementet og innhente antall sifre i det elementet. Det gir oss antall iterasjoner sorteringsprosessen vil følge.
• Grupper de individuelle sifrene til elementene på samme signifikante posisjon i hver iterasjon.
• Grupperingsprosessen starter fra det minst signifikante sifferet og slutter ved det mest signifikante sifferet.
• Sortering av elementene basert på sifre på den signifikante posisjonen.
• Opprettholde den relative rekkefølgen av elementer som har samme nøkkelverdi. Denne egenskapen til radix-sorten gjør den til en stabil sort.

Den siste iterasjonen vil gi oss en fullstendig sortert liste.

Arbeid av Radix Sort Algorithm

La oss prøve å sortere listen over heltall i figuren ovenfor i stigende rekkefølge ved å bruke Radix Sort-algoritmen.

Her er trinnene for å utføre Radix-sorteringsprosessen:

Trinn 1) Identifiser elementet med maksimumsverdien i listen. I dette tilfellet er det 835.

Trinn 2) Beregn antall sifre for det maksimale elementet. 835 har 3 sifre nøyaktig.

Trinn 3) Bestem antall iterasjoner basert på trinn 2. 835 har 3 sifre, noe som betyr at antall iterasjoner vil være 3.

Trinn 4) Bestem bunnen av elementene. Siden dette er et desimalsystem, vil grunntallet være 10.

Trinn 5) Start den første iterasjonen.

a) Første iterasjon

I den første iterasjonen tar vi for oss enhetsplassverdien til hvert element.

Trinn 1) Modus heltallet med 10 for å få enhetsplassen til elementene. For eksempel gir 623 mod 10 oss verdien 3, og 248 mod 10 gir oss 8.

Trinn 2) Bruk tellesort eller annen stabil sortering for å organisere heltallene i henhold til deres minst signifikante siffer. Som det fremgår av figuren, vil 248 falle på den 8. bøtten. 623 vil falle på den tredje bøtten og så videre.

Etter den første iterasjonen ser listen nå slik ut.

Som du kan se fra figuren ovenfor, er listen ikke sortert ennå og krever mer iterasjon for å bli fullstendig sortert.

b) Andre iterasjon

I denne iterasjonen vil vi vurdere sifferet ved 10^th sted for sorteringsprosessen.

Trinn 1) Del heltallene på 10. 248 delt på 10 gir oss 24.

Trinn 2) Modus utgangen fra trinn 1 med 10. 24 mod 10 gir oss 4.

Trinn 3) Følg trinn 2 fra forrige iterasjon.

Etter den andre iterasjonen ser listen nå slik ut

Du kan se fra figuren ovenfor at listen fortsatt ikke er helt sortert siden den ikke er i stigende rekkefølge ennå.

c) Tredje iterasjon

For den siste iterasjonen ønsker vi å få det mest signifikante sifferet. I dette tilfellet er det 100^th plass for hvert av heltallene i listen.

Trinn 1) Del heltallene med 100... 415 delt på 100 gir oss 4.

Trinn 2) Modus resultatet fra trinn 1 med 10. 4 mod 10 gir oss 4 igjen.

Trinn 3) Følg trinn 3 fra forrige iterasjon.

Som vi kan se, er listen sortert nå i stigende rekkefølge. Den siste iterasjonen er fullført, og sorteringsprosessen er nå ferdig.

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 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 for å implementere 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);
}

Utgang:

162 248 415 623 835

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

Utgang:

[162,248,415,623,835]

Kompleksitetsanalyse av Radix Sort

Det er to typer kompleksitet å vurdere, romkompleksitet og tidskompleksitet.

• Romkompleksitet: O(n+b) der n er størrelsen på matrisen og b er basen som vurderes.
• Tidskompleksitet: O(d*(n+b)) hvor d er antall sifre til det største elementet i matrisen.

Romkompleksiteten til Radix Sort

To funksjoner å fokusere på for plasskompleksitet

• Antall elementer i matrisen, n.
• Grunnlaget for å representere elementene, b.

Noen ganger kan denne basen være større enn størrelsen på matrisen.

Den totale kompleksiteten er dermed O(n+b).

Følgende egenskaper til elementene i listen kan gjøre radix-sortering ineffektiv:

• Elementer med et stort antall sifre.
• Basen av elementene er stor, som 64-bit tall.

Tidskompleksiteten til Radix Sort

Du kan bruke tellesorteringen som en subrutine, da hver iterasjon vil tae O(n+b) tid. Hvis det finnes d iterasjoner, blir den totale kjøretiden O(d*(n+b)). Her betyr "O" kompleksitetsfunksjonen.

Linearitet av Radix Sort

Radix Sort er lineær når

• d er konstant, der d er antall sifre i det største elementet.
• b er ikke større i stor grad sammenlignet med n.

Sammenligninger av Radix Sort med andre komparative algoritmer

Som vi har sett, er Radix-sortens kompleksitet basert på et ord- eller tallstørrelse. Det vil ha samme kompleksitet for de gjennomsnittlige og beste tilfellene. Og det er O(d*(n+b)). Dessuten er det forskjellig i henhold til sorteringsteknikken du bruker i midten. Du kan for eksempel bruke tellesortering eller hurtigsortering for den mellomliggende sorteringsalgoritmen inne i Radix-sorteringen.

Anvendelser av Radix Sort Algorithm

Viktige bruksområder for Radix Sort er:

• Radix Sort kan brukes som en stedsfinnende algoritme der store verdiområder brukes.
• Den brukes til å konstruere en suffiksmatrise i DC3-algoritmen.
• Den brukes i en sekvensiell, tilfeldig tilgangsmaskin som er tilstede i en typisk datamaskin der poster tastes inn.