Radix-Sortieralgorithmus in der Datenstruktur

Was ist der Radix-Sort-Algorithmus?

Radix Sort ist ein nicht-vergleichender Sortieralgorithmus. Er funktioniert durch Gruppierung.ping Die einzelnen Ziffern der zu sortierenden Elemente werden ermittelt. Anschließend werden die Elemente mithilfe eines stabilen Sortierverfahrens nach ihrer Basis geordnet. Es handelt sich um einen linearen Sortieralgorithmus.

Beim Sortiervorgang werden folgende Eigenschaften berücksichtigt:

• Das größte Element wird ermittelt und dessen Ziffernanzahl bestimmt. Daraus ergibt sich die Anzahl der Iterationen des Sortierprozesses.
• Grouping die einzelnen Ziffern der Elemente an der gleichen signifikanten Stelle in jeder Iteration.
• Die Gruppeping Der Prozess beginnt mit der niedrigstwertigen Ziffer und endet mit der höchstwertigen Ziffer.
• Die Elemente werden anhand der Ziffern an der entsprechenden Stelle sortiert.
• Die relative Reihenfolge der Elemente mit demselben Schlüsselwert bleibt erhalten. Diese Eigenschaft macht Radix Sort zu einem stabilen Sortierverfahren.

Die letzte Iteration liefert eine vollständig sortierte Liste.

Funktionsweise des Radix-Sortieralgorithmus

Liste der zu sortierenden Ganzzahlen

Sortieren wir die Liste der ganzen Zahlen in der obigen Abbildung mithilfe des Radixsort-Verfahrens in aufsteigender Reihenfolge.

Hier sind die Schritte zur Durchführung des Radix-Sort-Verfahrens:

Schritt 1) Ermitteln Sie das größte Element in der Liste. Hier ist es 835.

Schritt 2) Zähle die Ziffern. 835 hat 3 Ziffern, also ist die Anzahl der Iterationen 3.

Schritt 3) Bestimme die Basis. Da es sich um eine Dezimalzahl handelt, ist die Basis 10.

Schritt 4) Starten Sie die erste Iteration.

a) Erste Iteration

Sortierung nach der letzten Ziffer

In der ersten Iteration betrachten wir den Einheitsstellenwert jedes Elements.

Schritt 1) Man berechnet den Modulo der ganzen Zahl durch 10, um die Einerstelle der Elemente zu erhalten. Zum Beispiel ergibt 623 mod 10 3 und 248 mod 10 ergibt 8.

Schritt 2) Ordnen Sie die ganzen Zahlen mithilfe eines Zählsortierverfahrens oder eines anderen stabilen Sortierverfahrens nach ihrer niedrigstwertigen Stelle. Aus der Abbildung geht hervor, dass 248 in den 8. Behälter, 623 in den 3. Behälter usw. fällt.

Nach der ersten Iteration sieht die Liste nun so aus.

Liste nach der ersten Iteration

Die Liste ist noch nicht sortiert und erfordert weitere Iterationen.

b) Zweite Iteration

Sortierung nach Ziffern an der Zehnerstelle

In diesem Iterationsschritt betrachten wir die Ziffer an der Zehnerstelle für den Sortierprozess.

Schritt 1) Teile die ganzen Zahlen durch 10. Zum Beispiel ergibt 248 geteilt durch 10 gleich 24.

Schritt 2) Das Ergebnis von Schritt 1 wird modulo 10 berechnet. 24 mod 10 ergibt 4.

Schritt 3) Folgen Sie Schritt 2 aus der vorherigen Iteration.

Nach der zweiten Iteration sieht die Liste nun folgendermaßen aus:

Liste nach der zweiten Iteration

Die Liste ist noch nicht vollständig sortiert, da sie noch nicht aufsteigend geordnet ist.

c) Dritte Iteration

Sortierung anhand der Ziffern an der Hunderterstelle

Im letzten Schritt wollen wir die höchstwertige Ziffer ermitteln. In diesem Fall ist das die Hunderterstelle jeder ganzen Zahl in der Liste.

Schritt 1) Teile die ganzen Zahlen durch 100. Zum Beispiel ergibt 415 geteilt durch 100 gleich 4.

Schritt 2) Das Ergebnis aus Schritt 1 wird modulo 10 berechnet. 4 mod 10 ergibt 4.

Schritt 3) Folgen Sie Schritt 3 aus der vorherigen Iteration.

Liste nach der dritten Iteration

Die Liste ist nun aufsteigend sortiert. Der letzte Durchlauf ist abgeschlossen und der Sortiervorgang beendet.

Pseudocode des Radix-Sortieralgorithmus

Hier ist der Pseudocode für den Radixsort-Algorithmus:

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 zur Implementierung von 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);
}

Ausgang:

162 248 415 623 835

Python Programm für den Radix-Sort-Algorithmus

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

Ausgang:

[162, 248, 415, 623, 835]

Komplexitätsanalyse des Radixsort-Verfahrens

Es sind zwei Arten von Komplexität zu berücksichtigen: die räumliche Komplexität und die zeitliche Komplexität.

• Raumkomplexität: O(n + b) wobei n die Größe des Arrays und b die betrachtete Basis ist.
• Zeitkomplexität: O(d * (n + b)), wobei d die Anzahl der Ziffern des größten Elements im Array ist.

Platzkomplexität der Radixsortierung

Zwei Merkmale, auf die man sich hinsichtlich der Speicherkomplexität konzentrieren sollte:

• Anzahl der Elemente im Array, n.
• Die Basis, die zur Darstellung der Elemente verwendet wird, b.

Manchmal kann diese Basis größer sein als die Größe des Arrays. Die Gesamtkomplexität beträgt somit O(n + b).

Die folgenden Eigenschaften der Elemente in der Liste können dazu führen, dass Radix Sort speicherineffizient ist:

• Elemente mit einer großen Anzahl von Ziffern.
• Die Basis der Elemente ist groß, wie 64-Bit-Zahlen.

Zeitliche Komplexität der Radixsortierung

Bei Verwendung von Counting Sort als Unterprogramm dauert jede Iteration O(n + b) Zeit. Wenn Iterationen vorhanden sind, beträgt die Gesamtlaufzeit O(d * (n + b))Hierbei bezeichnet „O“ die Komplexitätsfunktion.

Linearität der Radix-Sortierung

Radixsort ist linear, wenn:

• d ist konstant, wobei d die Anzahl der Stellen des größten Elements ist.
• b ist nicht wesentlich größer als n.

Vergleich des Radixsort-Verfahrens mit anderen Sortierverfahren Algorithms

Die Komplexität des Radixsort-Algorithmus hängt von der Anzahl der Zahlen ab. Sowohl im besten als auch im durchschnittlichen Fall beträgt sie O(d * (n + b)). Die Leistung variiert je nach innerem Sortieralgorithmus – Countingsort ist Standard, aber jeder stabile Sortieralgorithmus ist geeignet.

Anwendungen des Radix-Sort-Algorithmus

Wichtige Anwendungsgebiete des Radixsort-Verfahrens sind:

• Radix Sort kann als Ortsfindungsalgorithmus verwendet werden, wenn große Wertebereiche involviert sind.
• Es wird verwendet, um im DC3-Algorithmus ein Suffix-Array zu erstellen.
• Es wird in sequenziellen, wahlfreien Zugriffsmaschinen verwendet, bei denen Datensätze durch Kennungen fester Breite indiziert werden.

Häufig gestellte Fragen