Radix-sorteringsalgoritme i datastruktur

Hvad er Radix Sort Algorithm?

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

Sorteringsprocessen involverer følgende egenskaber:

• Find det maksimale element og få antallet af cifre for det element. Dette giver antallet af iterationer, som sorteringsprocessen udfører.
• Grouping de individuelle cifre for elementerne på samme betydende position i hver iteration.
• Gruppenping Processen starter med det mindst betydende ciffer og slutter ved det mest betydende ciffer.
• Sortering af elementerne baseret på cifrene på den betydende position.
• Bevarer den relative rækkefølge af elementer, der har samme nøgleværdi. Denne egenskab ved Radix Sort gør den til en stabil sortering.

Den sidste iteration returnerer en fuldstændig sorteret liste.

Arbejde med Radix Sort Algorithm

Liste over heltal, der skal sorteres

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

Her er trinnene til at udføre Radix Sort-processen:

Trin 1) Identificér det største element på listen. Her er det 835.

Trin 2) Tæl dets cifre. 835 har 3 cifre, så antallet af iterationer er 3.

Trin 3) Bestem grundtallet. Da dette er et decimaltal, er grundtallet 10.

Trin 4) Start den første iteration.

a) Første iteration

Sortering efter sidste ciffer

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

Trin 1) Modificer heltallet med 10 for at få elementernes enhedsplads. For eksempel giver 623 mod 10 3, og 248 mod 10 giver 8.

Trin 2) Brug tællesortering eller en anden stabil sortering til at organisere heltallene efter deres mindst betydende ciffer. Ud fra figuren falder 248 i den 8. kategori, 623 falder i den 3. kategori, og så videre.

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

Liste efter den første iteration

Listen er ikke sorteret endnu og kræver flere iterationer.

b) Anden iteration

Sortering baseret på cifre på tiere

I denne iteration betragter vi cifferet på tierpladsen i sorteringsprocessen.

Trin 1) Divider de heltale med 10. For eksempel giver 248 divideret med 10 24.

Trin 2) Modificer outputtet fra trin 1 med 10. 24 mod 10 giver 4.

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

Efter den anden iteration ser listen nu således ud:

Liste efter anden iteration

Listen er endnu ikke helt sorteret, da den ikke er i stigende rækkefølge.

c) Tredje iteration

Sortering baseret på cifrene på hundredpladsen

I den sidste iteration ønsker vi at få det mest betydende ciffer. I dette tilfælde er det hundredtallet for hvert af heltallene i listen.

Trin 1) Divider de heltale med 100. For eksempel giver 415 divideret med 100 4.

Trin 2) Modificer resultatet fra trin 1 med 10. 4 mod 10 giver 4.

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

Liste efter tredje iteration

Listen er nu sorteret i stigende rækkefølge. Den sidste iteration er fuldført, og sorteringsprocessen er afsluttet.

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

Output:

162 248 415 623 835

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

Output:

[162, 248, 415, 623, 835]

Kompleksitethedsanalyse 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 grundtal.
• 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å i forbindelse med rumkompleksitet:

• Antal elementer i arrayet, n.
• Basen, der bruges til at repræsentere elementerne, b.

Nogle gange kan denne base være større end størrelsen af ​​arrayet. Den samlede kompleksitet er således O(n + b).

Følgende egenskaber ved elementerne i listen kan gøre Radix Sort-rummet ineffektivt:

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

Tidskompleksitet af Radix Sort

Ved at bruge tællende sortering som en subrutine, tager hver iteration O(n + b) tid. Hvis der findes d iterationer, bliver den samlede køretid O(d * (n + b))Her betegner "O" kompleksitetsfunktionen.

Linearitet af Radix Sort

Radixsortering er lineær når:

• d er konstant, hvor d er antallet af cifre i det største grundstof.
• b er ikke væsentligt større end n.

Sammenligning af Radix Sort med anden sortering Algorithms

Radix Sorts kompleksitet afhænger af tallets størrelse. Bedste-case og average-case er begge O(d * (n + b)). Ydeevnen varierer med den indre sortering — tællesortering er standard, men enhver stabil sortering fungerer.

Anvendelser af Radix Sort Algorithm

Vigtige anvendelser af Radix Sort er:

• Radix Sort kan bruges som en lokationsfindingsalgoritme, hvor store værdiintervaller er involveret.
• Det bruges til at konstruere et suffiksarray i DC3-algoritmen.
• Det bruges i sekventielle maskiner med tilfældig adgang, hvor poster indtastes med identifikatorer med fast bredde.

Ofte Stillede Spørgsmål