Radix-sorteeralgoritme in gegevensstructuur

Wat is het Radix sorteeralgoritme?

Radix Sort is een niet-vergelijkend sorteeralgoritme. Het werkt door middel van groepering...ping De afzonderlijke cijfers van de te sorteren elementen worden vastgelegd. Vervolgens wordt een stabiele sorteertechniek gebruikt om de elementen te ordenen op basis van hun grondtal. Dit is een lineair sorteeralgoritme.

Het sorteerproces omvat de volgende eigenschappen:

• Het maximale element vinden en het aantal cijfers van dat element bepalen. Dit geeft het aantal iteraties dat het sorteerproces uitvoert.
• Grouping de afzonderlijke cijfers van de elementen op dezelfde significante positie in elke iteratie.
• De groepping Het proces begint bij het minst significante cijfer en eindigt bij het meest significante cijfer.
• De elementen sorteren op basis van de cijfers op die significante positie.
• Het behouden van de relatieve volgorde van elementen met dezelfde sleutelwaarde. Deze eigenschap van Radix Sort maakt het een stabiele sorteermethode.

De laatste iteratie levert een volledig gesorteerde lijst op.

Werking van het Radix Sort-algoritme

Lijst met gehele getallen die moeten worden gesorteerd

Laten we de lijst met gehele getallen in de bovenstaande afbeelding sorteren in oplopende volgorde met behulp van Radix Sort.

Hieronder volgen de stappen om het Radix Sort-proces uit te voeren:

Stap 1) Bepaal het grootste element in de lijst. In dit geval is dat 835.

Stap 2) Tel de cijfers. 835 heeft 3 cijfers, dus het aantal iteraties is 3.

Stap 3) Bepaal het grondgetal. Omdat dit een decimaal getal is, is het grondgetal 10.

Stap 4) Start de eerste iteratie.

a) Eerste iteratie

Sorteren op het laatste cijfer

In de eerste iteratie houden we rekening met de eenheidswaarde van elk element.

Stap 1) Neem de modulo-operator van het getal 10 om de eenheden van de elementen te krijgen. Bijvoorbeeld, 623 modulo 10 geeft 3, en 248 modulo 10 geeft 8.

Stap 2) Gebruik telsortering of een andere stabiele sorteermethode om de getallen te ordenen op basis van hun minst significante cijfer. In de afbeelding valt 248 in de 8e emmer, 623 in de 3e emmer, enzovoort.

Na de eerste iteratie ziet de lijst er nu als volgt uit.

Lijst na de eerste iteratie

De lijst is nog niet gesorteerd en vereist meer iteraties.

b) Tweede iteratie

Sortering op basis van cijfers op de plaats van de tientallen

In deze iteratie houden we rekening met het cijfer op de tientallenpositie voor het sorteerproces.

Stap 1) Deel de getallen door 10. Bijvoorbeeld, 248 gedeeld door 10 is 24.

Stap 2) Modulo de uitkomst van stap 10. 24 modulo 10 geeft 4.

Stap 3) Volg stap 2 van de vorige iteratie.

Na de tweede iteratie ziet de lijst er nu als volgt uit:

Lijst na de tweede iteratie

De lijst is nog niet volledig gesorteerd, omdat deze nog niet in oplopende volgorde staat.

c) Derde iteratie

Sorteren op basis van de cijfers op de honderdste plaats.

Voor de laatste iteratie willen we het meest significante cijfer bepalen. In dit geval is dat het honderdtal van elk getal in de lijst.

Stap 1) Deel de getallen door 100. Bijvoorbeeld, 415 gedeeld door 100 is 4.

Stap 2) Modulo het resultaat van stap 10. 4 modulo 10 geeft 4.

Stap 3) Volg stap 3 van de vorige iteratie.

Lijst na de derde iteratie

De lijst is nu gesorteerd in oplopende volgorde. De laatste iteratie is voltooid en het sorteerproces is afgerond.

Pseudocode van Radix Sorteeralgoritme

Hier volgt de pseudocode voor het Radix Sort-algoritme:

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++ Programma om Radix Sort te implementeren

#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 Programma voor Radix Sorteeralgoritme

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

Complexiteitsanalyse van Radix Sort

Er zijn twee soorten complexiteit waarmee rekening moet worden gehouden: ruimtecomplexiteit en tijdscomplexiteit.

• Ruimtecomplexiteit: O(n + b), waarbij n de grootte van de array is en b het beschouwde grondtal.
• Tijdcomplexiteit: O(d * (n + b)) waarbij d het aantal cijfers is van het grootste element in de array.

Ruimtecomplexiteit van radixsortering

Twee kenmerken om op te letten bij het bepalen van de ruimtecomplexiteit:

• Aantal elementen in de array, n.
• De basis die gebruikt wordt om de elementen weer te geven, b.

Soms kan deze basis groter zijn dan de grootte van de array. De totale complexiteit is dan O(n + b).

De volgende eigenschappen van de elementen in de lijst kunnen ervoor zorgen dat Radix Sort ruimte-inefficiënt wordt:

• Elementen met een groot aantal cijfers.
• De basis van de elementen is groot, zoals 64-bits getallen.

Tijdcomplexiteit van radixsortering

Bij gebruik van counting sort als subroutine duurt elke iteratie O(n + b) tijd. Als er iteraties bestaan, wordt de totale looptijd O(d * (n + b))Hier staat “O” voor de complexiteitsfunctie.

Lineariteit van Radix-sortering

Radix Sort is lineair wanneer:

• d is constant, waarbij d het aantal cijfers van het grootste element is.
• b is niet significant groter dan n.

Vergelijking van Radix Sort met andere sorteermethoden Algorithms

De complexiteit van Radix Sort hangt af van de grootte van de getallen. Zowel in het beste geval als in het gemiddelde geval is de complexiteit O(d * (n + b)). De prestaties variëren afhankelijk van de interne sorteermethode — telsortering is standaard, maar elke stabiele sorteermethode werkt.

Toepassingen van het Radix Sort-algoritme

Belangrijke toepassingen van Radix Sort zijn:

• Radixsort kan worden gebruikt als een algoritme voor het vinden van locaties wanneer grote reeksen waarden betrokken zijn.
• Het wordt gebruikt om een ​​suffix-array te construeren in het DC3-algoritme.
• Het wordt gebruikt in sequentiële, willekeurige toegangssystemen waarbij records worden gekoppeld aan identificatoren met een vaste breedte.

Veelgestelde vragen