Radix algoritam sortiranja u strukturi podataka

Što je Radix algoritam sortiranja?

Radix Sort je algoritam sortiranja koji nije komparativni. Radi po grupnoj metodi.ping pojedinačne znamenke elemenata koje treba sortirati. Zatim se koristi stabilna tehnika sortiranja za organiziranje elemenata na temelju njihovog radiksa. To je linearni algoritam sortiranja.

Proces sortiranja uključuje sljedeća svojstva:

• Pronalaženje maksimalnog elementa i dobivanje broja znamenki tog elementa. To daje broj iteracija koje proces sortiranja izvodi.
• Grouping pojedinačne znamenke elemenata na istoj značajnoj poziciji u svakoj iteraciji.
• Grupaping Proces počinje od najmanje značajne znamenke, a završava na najznačajnijoj znamenki.
• Sortiranje elemenata na temelju znamenki na toj značajnoj poziciji.
• Održavanje relativnog redoslijeda elemenata koji imaju istu ključnu vrijednost. Ovo svojstvo Radix sortiranja čini ga stabilnim sortiranjem.

Završna iteracija vraća potpuno sortiranu listu.

Rad algoritma radix sortiranja

Popis cijelih brojeva koje treba sortirati

Sortirajmo popis cijelih brojeva na gornjoj slici uzlaznim redoslijedom koristeći Radix Sort.

Evo koraka za izvođenje postupka Radix sortiranja:

Korak 1) Odredite maksimalni element na popisu. Ovdje je to 835.

Korak 2) Prebroji njegove znamenke. Broj 835 ima 3 znamenke, pa je broj iteracija 3.

Korak 3) Odredite bazu. Budući da je ovo decimalni broj, baza je 10.

Korak 4) Započnite prvu iteraciju.

a) Prva iteracija

Sortiranje po zadnjoj znamenki

U prvoj iteraciji razmatramo jediničnu vrijednost svakog elementa.

Korak 1) Modificirajte cijeli broj za 10 da biste dobili jedinični položaj elemenata. Na primjer, 623 mod 10 daje 3, a 248 mod 10 daje 8.

Korak 2) Koristite sortiranje brojanjem ili neko drugo stabilno sortiranje za organiziranje cijelih brojeva prema njihovoj najmanje značajnoj znamenki. Iz slike, 248 spada u 8. skupinu, 623 spada u 3. skupinu i tako dalje.

Nakon prve iteracije lista sada izgleda ovako.

Popis nakon prve iteracije

Popis još nije sortiran i zahtijeva više iteracija.

b) Druga iteracija

Sortiranje na temelju znamenki na mjestu desetica

U ovoj iteraciji, za proces sortiranja uzimamo u obzir znamenku na mjestu desetica.

Korak 1) Podijelite cijele brojeve s 10. Na primjer, 248 podijeljeno s 10 daje 24.

Korak 2) Izlaz iz 1. koraka modificirajte s 10. 24 mod 10 daje 4.

Korak 3) Slijedite korak 2 iz prethodne iteracije.

Nakon druge iteracije, popis sada izgleda ovako:

Popis nakon druge iteracije

Popis još nije u potpunosti sortiran jer nije u uzlaznom redoslijedu.

c) Treća iteracija

Sortiranje na temelju znamenki na mjestu stotica

Za posljednju iteraciju želimo dobiti najznačajniju znamenku. U ovom slučaju, to je mjesto stotica za svaki od cijelih brojeva na popisu.

Korak 1) Podijelite cijele brojeve s 100. Na primjer, 415 podijeljeno s 100 daje 4.

Korak 2) Rezultat iz 1. koraka modificirajte s 10. 4 mod 10 daje 4.

Korak 3) Slijedite korak 3 iz prethodne iteracije.

Popis nakon trećeg ponavljanja

Popis je sada sortiran uzlaznim redoslijedom. Završna iteracija je završena i proces sortiranja je završen.

Pseudokod Radix algoritma sortiranja

Evo pseudokoda za algoritam sortiranja Radix:

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 za implementaciju Radix sortiranja

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

Izlaz:

162 248 415 623 835

Python Program za Radix algoritam sortiranja

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

Izlaz:

[162, 248, 415, 623, 835]

Analiza složenosti Radix sortiranja

Postoje dvije vrste složenosti koje treba uzeti u obzir: prostorna složenost i vremenska složenost.

• Složenost prostora: O(n + b) gdje je n veličina polja, a b je razmatrana baza.
• Vremenska složenost: O(d * (n + b)) gdje je d broj znamenki najvećeg elementa u nizu.

Prostorna složenost radix sortiranja

Dvije značajke na koje se treba usredotočiti kod prostorne složenosti:

• Broj elemenata u nizu, n.
• Baza koja se koristi za predstavljanje elemenata, b.

Ponekad ova baza može biti veća od veličine polja. Ukupna složenost je stoga O(n + b).

Sljedeća svojstva elemenata na popisu mogu učiniti prostor Radix Sort neučinkovitim:

• Elementi s velikim brojem znamenki.
• Baza elemenata je velika, poput 64-bitnih brojeva.

Vremenska složenost radix sortiranja

Korištenjem sortiranja brojanjem kao potprograma, svaka iteracija traje O(n + b) vrijeme. Ako postoje iteracije, ukupno vrijeme rada postaje O(d * (n + b))Ovdje "O" označava funkciju složenosti.

Linearnost radix sortiranja

Radix sortiranje je linearno kada:

• d je konstanta, gdje je d broj znamenki najvećeg elementa.
• b nije znatno veći od n.

Usporedba Radix sortiranja s drugim sortiranjima Algorithms

Složenost Radix sortiranja ovisi o veličini broja. Najbolji i prosječni slučaj su oba O(d * (n + b)). Performanse variraju ovisno o unutarnjem sortiranju - sortiranje brojanjem je standardno, ali bilo koje stabilno sortiranje radi.

Primjene Radix algoritma sortiranja

Važne primjene Radix sortiranja su:

• Radix sortiranje se može koristiti kao algoritam za pronalaženje lokacije gdje su uključeni veliki rasponi vrijednosti.
• Koristi se za konstruiranje sufiksnog niza u DC3 algoritmu.
• Koristi se u sekvencijalnim strojevima s nasumičnim pristupom gdje su zapisi označeni identifikatorima fiksne širine.

Pitanja i odgovori