Radix-sorteringsalgoritm i datastruktur

Vad är Radix Sort Algorithm?

Radix Sort är en icke-jämförande sorteringsalgoritm. Den fungerar genom att grupperaping de individuella siffrorna för de element som ska sorteras. En stabil sorteringsteknik används sedan för att organisera elementen baserat på deras radix. Det är en linjär sorteringsalgoritm.

Sorteringsprocessen innefattar följande egenskaper:

• Hitta det maximala elementet och få antalet siffror för det elementet. Detta ger antalet iterationer som sorteringsprocessen utför.
• Grouping de individuella siffrorna för elementen på samma signifikanta position i varje iteration.
• Gruppenping Processen börjar från den minst signifikanta siffran och slutar vid den mest signifikanta siffran.
• Sortera elementen baserat på siffrorna på den signifikanta positionen.
• Bibehåller den relativa ordningen av element som har samma nyckelvärde. Denna egenskap hos Radix Sort gör den till en stabil sortering.

Den sista iterationen returnerar en fullständigt sorterad lista.

Fungerar av Radix Sort Algorithm

Lista över heltal som ska sorteras

Låt oss sortera listan med heltal i figuren ovan i stigande ordning med hjälp av Radix Sort.

Här är stegen för att utföra Radix Sort-processen:

Steg 1) Identifiera det största elementet i listan. Här är det 835.

Steg 2) Räkna dess siffror. 835 har 3 siffror, så antalet iterationer är 3.

Steg 3) Bestäm basen. Eftersom detta är decimalt är basen 10.

Steg 4) Starta den första iterationen.

a) Första iterationen

Sortering efter sista siffran

I den första iterationen tar vi hänsyn till enhetsplatsvärdet för varje element.

Steg 1) Modifiera heltalet med 10 för att få elementens enhetsplats. Till exempel ger 623 mod 10 3 och 248 mod 10 ger 8.

Steg 2) Använd räknesortering eller annan stabil sortering för att organisera heltalen enligt deras minst signifikanta siffra. Från figuren faller 248 i den åttonde hink, 623 i den tredje hink, och så vidare.

Efter den första iterationen ser listan nu ut så här.

Lista efter den första iterationen

Listan är ännu inte sorterad och kräver fler iterationer.

b) Andra iterationen

Sortering baserat på siffror på tiotalsplats

I denna iteration betraktar vi siffran på tiotalsplatsen för sorteringsprocessen.

Steg 1) Dividera heltalen med 10. Till exempel, 248 dividerat med 10 ger 24.

Steg 2) Modifiera utdata från steg 1 med 10. 24 mod 10 ger 4.

Steg 3) Följ steg 2 från föregående iteration.

Efter den andra iterationen ser listan nu ut så här:

Lista efter den andra iterationen

Listan är ännu inte helt sorterad eftersom den inte är i stigande ordning.

c) Tredje iterationen

Sortering baserat på siffrorna på hundraplats

För den sista iterationen vill vi få den mest signifikanta siffran. I det här fallet är det hundratalsplatsen för varje heltal i listan.

Steg 1) Dividera heltalen med 100. Till exempel, 415 dividerat med 100 ger 4.

Steg 2) Modifiera resultatet från steg 1 med 10. 4 mod 10 ger 4.

Steg 3) Följ steg 3 från föregående iteration.

Lista efter den tredje iterationen

Listan är nu sorterad i stigande ordning. Den sista iterationen är slutförd och sorteringsprocessen är avslutad.

Pseudokod för Radix Sort Algorithm

Här är pseudokoden för 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 för att implementera 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);
}

Produktion:

162 248 415 623 835

Python Program för 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)

Produktion:

[162, 248, 415, 623, 835]

Komplexitetsanalys av Radix Sort

Det finns två typer av komplexitet att beakta: rumskomplexitet och tidskomplexitet.

• Rymdkomplexitet: O(n + b) där n är storleken på matrisen och b är basen som beaktas.
• Tidskomplexitet: O(d * (n + b)) där d är antalet siffror för det största elementet i arrayen.

Space Complexity of Radix Sort

Två funktioner att fokusera på för rymdkomplexitet:

• Antal element i arrayen, n.
• Basen som används för att representera elementen, b.

Ibland kan denna bas vara större än arrayens storlek. Den totala komplexiteten är således O(n + b).

Följande egenskaper hos elementen i listan kan göra Radix Sort-utrymmet ineffektivt:

• Element med ett stort antal siffror.
• Basen av elementen är stor, som 64-bitars tal.

Tidskomplexitet hos Radix Sort

Med räknesortering som subrutin tar varje iteration O(n + b) tid. Om d iterationer finns blir den totala körtiden O(d * (n + b))Här betecknar "O" komplexitetsfunktionen.

Linjäritet för Radix Sort

Radixsortering är linjär när:

• d är konstant, där d är antalet siffror i det största elementet.
• b är inte betydligt större än n.

Jämförelse av Radix Sort med annan sortering Algorithms

Radix Sorts komplexitet beror på numrets storlek. Bästa-fall och medelfall är båda O(d * (n + b)). Prestandan varierar med den inre sorteringen — räknesortering är standard, men vilken stabil sortering som helst fungerar.

Tillämpningar av Radix Sort Algorithm

Viktiga tillämpningar av Radix Sort är:

• Radix Sort kan användas som en platssökningsalgoritm där stora värdeintervall är inblandade.
• Den används för att konstruera en suffixmatris i DC3-algoritmen.
• Den används i sekventiella maskiner med slumpmässig åtkomst där poster nycklas med identifierare med fast bredd.

Vanliga frågor