Radix sortimise algoritm andmestruktuuris

Mis on Radixi sortimise algoritm?

Radix Sort on mittevõrdlev sortimisalgoritm. See töötab rühmade kaupa.ping sorteeritavate elementide üksikud numbrid. Seejärel kasutatakse elementide korraldamiseks nende radixi alusel stabiilset sortimistehnikat. See on lineaarne sortimisalgoritm.

Sorteerimisprotsess hõlmab järgmisi omadusi:

• Maksimaalse elemendi leidmine ja selle elemendi numbrite arvu saamine. See annab sortimisprotsessi käigus tehtavate iteratsioonide arvu.
• Grouping iga iteratsiooni samal olulisel positsioonil olevate elementide üksikud numbrid.
• Sahjuping Protsess algab kõige väiksema tähtsusega numbrist ja lõpeb kõige suurema tähtsusega numbriga.
• Elementide sorteerimine selle olulise positsiooni numbrite põhjal.
• Sama võtmeväärtusega elementide suhtelise järjestuse säilitamine. See Radix Sorti omadus muudab selle stabiilseks sortimiseks.

Viimane iteratsioon tagastab täielikult sorteeritud loendi.

Radixi sortimise algoritmi töö

Sorteeritavate täisarvude loend

Sorteerime ülaltoodud joonisel olevad täisarvud radikaalsortimise abil kasvavas järjekorras.

Radixi sortimise protsessi teostamiseks toimige järgmiselt.

Step 1) Tuvasta loendi suurim element. Siin on see 835.

Step 2) Loe selle numbrid kokku. Arv 835 on kolmekohaline, seega on iteratsioonide arv 3.

Step 3) Määrake alus. Kuna see on kümnendmurd, on alus 10.

Step 4) Alustage esimest iteratsiooni.

a) Esimene iteratsioon

Sorteerimine viimase numbri järgi

Esimeses iteratsioonis arvestame iga elemendi ühikulise kohaväärtusega.

Step 1) Elementide ühikukoha saamiseks modifitseeri täisarvu 10 võrra. Näiteks 623 mod 10 annab tulemuseks 3 ja 248 mod 10 annab tulemuseks 8.

Step 2) Kasutage loendamissortimist või muud stabiilset sortimist, et korraldada täisarvud nende vähimolulise numbri järgi. Jooniselt langeb 248 8. ämbrisse, 623 3. ämbrisse jne.

Pärast esimest iteratsiooni näeb nimekiri nüüd välja selline.

Loetelu pärast esimest iteratsiooni

Nimekiri pole veel sorteeritud ja vajab rohkem kordamist.

b) Teine iteratsioon

Sorteerimine kümnendkoha numbrite alusel

Selles iteratsioonis vaatleme sortimisprotsessi jaoks kümneliste kohta.

Step 1) Jaga täisarvud 10-ga. Näiteks 248 jagamisel 10-ga saame 24.

Step 2) Modifitseeri 1. sammu väljundit 10 võrra. 24 modifitseeri 10 annab tulemuseks 4.

Step 3) Järgige eelmise iteratsiooni 2. sammu.

Pärast teist korda läbimist näeb nimekiri välja selline:

Nimekiri pärast teist iteratsiooni

Nimekiri pole veel täielikult sorteeritud, kuna see pole veel kasvavas järjekorras.

c) Kolmas iteratsioon

Sorteerimine sajaliste numbrite järgi

Viimase iteratsiooni jaoks tahame leida kõige olulisema numbri. Antud juhul on see iga loendis oleva täisarvu sajandik.

Step 1) Jaga täisarvud 100-ga. Näiteks 415 jagamisel 100-ga saame 4.

Step 2) Modifitseeri 1. sammu tulemust 10 võrra. 4 modifitseeri 10 annab tulemuseks 4.

Step 3) Järgige eelmise iteratsiooni 3. sammu.

Loetelu pärast kolmandat iteratsiooni

Loend on nüüd kasvavas järjekorras sorteeritud. Viimane iteratsioon on lõpule viidud ja sortimisprotsess on lõppenud.

Radixi sortimisalgoritmi pseudokood

Siin on Radixi sortimisalgoritmi pseudokood:

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++ Programm Radix Sorti rakendamiseks

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

Väljund:

162 248 415 623 835

Python Programm Radix Sort Algorithmi jaoks

# 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)

Väljund:

[162, 248, 415, 623, 835]

Radix-sortimise keerukusanalüüs

Arvesse tuleb võtta kahte tüüpi keerukust: ruumi keerukus ja aja keerukus.

• Ruumi keerukus: O(n + b), kus n on massiivi suurus ja b on vaadeldav baas.
• Ajaline keerukus: O(d * (n + b)), kus d on massiivi suurima elemendi numbrite arv.

Radixi sortimise ruumi keerukus

Ruumi keerukuse puhul tuleks keskenduda kahele omadusele:

• Massiivi elementide arv, n.
• Elementide kujutamiseks kasutatav alus, b.

Mõnikord võib see baas olla suurem kui massiivi suurus. Seega on üldine keerukus O(n + b).

Loendi elementide järgmised omadused võivad muuta Radixi sortimisruumi ebaefektiivseks:

• Suure arvu numbritega elemendid.
• Elementide alus on suur, nagu 64-bitised numbrid.

Radixi sortimise ajaline keerukus

Loendava sortimise kasutamisel alamprogrammina võtab iga iteratsioon aega O(n + b) aega. Kui d iteratsioonid on olemas, muutub kogu tööaeg O(d * (n + b))Siin tähistab „O” keerukusfunktsiooni.

Radixi sortimise lineaarsus

Radix-sortimine on lineaarne, kui:

• d on konstantne, kus d on suurima elemendi numbrite arv.
• b ei ole oluliselt suurem kui n.

Radixi sortimise võrdlus teiste sortimistega Algorithms

Radix-sortimise keerukus sõltub arvu suurusest. Nii parim kui ka keskmine juhtum on O(d * (n + b)). Jõudlus varieerub olenevalt sisemisest sortimisest – loendav sortimine on standardne, kuid iga stabiilne sortimine töötab.

Radixi sortimise algoritmi rakendused

Radix Sortimise olulised rakendused on:

• Radix Sortimist saab kasutada asukoha leidmise algoritmina, kui tegemist on suurte väärtusvahemikega.
• Seda kasutatakse DC3 algoritmis sufiksimassiivi konstrueerimiseks.
• Seda kasutatakse järjestikustes, muutpöördusega masinates, kus kirjed on võtmestatud fikseeritud laiusega identifikaatoritega.

KKK