Radix sorteringsalgoritme i datastruktur

Hva er Radix Sort Algorithm?

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

Sorteringsprosessen involverer følgende egenskaper:

• Finne det største elementet og få antall sifre for det elementet. Dette gir antall iterasjoner sorteringsprosessen utfører.
• Grouping de individuelle sifrene til elementene på samme signifikante posisjon i hver iterasjon.
• Gruppenping Prosessen starter med det minst signifikante sifferet og slutter med det mest signifikante sifferet.
• Sortering av elementene basert på sifrene på den signifikante posisjonen.
• Opprettholder den relative rekkefølgen av elementer som har samme nøkkelverdi. Denne egenskapen til Radix Sort gjør den til en stabil sortering.

Den siste iterasjonen returnerer en fullstendig sortert liste.

Arbeid av Radix Sort Algorithm

Liste over heltall som skal sorteres

La oss sortere listen over heltall i figuren ovenfor i stigende rekkefølge ved hjelp av Radix Sort.

Her er trinnene for å utføre Radix Sort-prosessen:

Trinn 1) Identifiser det største elementet i listen. Her er det 835.

Trinn 2) Tell sifrene. 835 har 3 sifre, så antallet iterasjoner er 3.

Trinn 3) Bestem grunntallet. Siden dette er et desimaltall, er grunntallet 10.

Trinn 4) Start den første iterasjonen.

a) Første iterasjon

Sortering etter siste siffer

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

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

Trinn 2) Bruk tellesortering eller en annen stabil sortering for å organisere heltallene etter deres minst signifikante siffer. Fra figuren faller 248 inn i den åttende kategorien, 623 faller inn i den tredje kategorien, og så videre.

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

Liste etter første iterasjon

Listen er ikke sortert ennå og krever flere iterasjoner.

b) Andre iterasjon

Sortering basert på sifre på tiere

I denne iterasjonen tar vi for oss sifferet på tiendeplassen i sorteringsprosessen.

Trinn 1) Del heltallene med 10. For eksempel gir 248 delt på 10 24.

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

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

Etter den andre iterasjonen ser listen nå slik ut:

Liste etter den andre iterasjonen

Listen er fortsatt ikke fullstendig sortert, da den ikke er i stigende rekkefølge ennå.

c) Tredje iterasjon

Sortering basert på sifrene på hundreplass

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

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

Trinn 2) Modifiser resultatet fra trinn 1 med 10. 4 mod 10 gir 4.

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

Liste etter den tredje iterasjonen

Listen er nå sortert i stigende rekkefølge. Den siste iterasjonen er fullført, og sorteringsprosessen er ferdig.

Pseudokode for Radix Sort Algorithm

Her er pseudokoden for Radix Sort-algoritmen:

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 in the jth place
    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 integer
    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 in 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

data = [162, 623, 835, 415, 248]
radixSortAlgo(data)
print(data)

Utgang:

[162, 248, 415, 623, 835]

Kompleksitethetsanalyse av Radix Sort

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

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

Romkompleksiteten til Radix Sort

To funksjoner å fokusere på for romkompleksitet:

• Antall elementer i matrisen, n.
• Basen som brukes til å representere elementene, b.

Noen ganger kan denne basen være større enn størrelsen på tabellen. Den totale kompleksiteten er dermed O(n + b).

Følgende egenskaper ved elementene i listen kan gjøre Radix Sort-plass ineffektiv:

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

Tidskompleksiteten til Radix Sort

Ved å bruke tellende sortering som en subrutine, tar hver iterasjon O(n + b) tid. Hvis det finnes d iterasjoner, blir den totale kjøretiden O(d * (n + b))Her betegner «O» kompleksitetsfunksjonen.

Linearitet av Radix Sort

Radixsortering er lineær når:

• d er konstant, der d er antall sifre i det største elementet.
• b er ikke vesentlig større enn n.

Sammenligning av Radix Sort med annen sortering Algorithms

Radix Sorts kompleksitet avhenger av tallstørrelsen. Best-case og average-case er begge O(d * (n + b)). Ytelsen varierer med den indre sorteringen – tellesortering er standard, men enhver stabil sortering fungerer.

Anvendelser av Radix Sort Algorithm

Viktige bruksområder for Radix Sort er:

• Radix Sort kan brukes som en algoritme for stedsfinning der store verdiområder er involvert.
• Den brukes til å konstruere en suffiksmatrise i DC3-algoritmen.
• Den brukes i sekvensielle maskiner med tilfeldig tilgang der poster tastes inn med identifikatorer med fast bredde.

Spørsmål og svar