Radix-Sortieralgorithmus in der Datenstruktur

Was ist der Radix-Sort-Algorithmus?

Radix Sort ist ein nicht vergleichender Sortieralgorithmus. Dabei werden die einzelnen Ziffern der zu sortierenden Elemente gruppiert. Anschließend wird eine stabile Sortiertechnik verwendet, um die Elemente basierend auf ihrer Basis zu organisieren. Es handelt sich um einen linearen Sortieralgorithmus.

Beim Sortiervorgang werden folgende Eigenschaften berücksichtigt:

Finden des maximalen Elements und Ermitteln der Anzahl der Ziffern dieses Elements. Es gibt uns die Anzahl der Iterationen an, denen der Sortierprozess folgen wird.
Gruppieren Sie die einzelnen Ziffern der Elemente in jeder Iteration an derselben signifikanten Position.
Der Gruppierungsprozess beginnt bei der niedrigstwertigen Ziffer und endet bei der höchstwertigen Ziffer.
Sortieren der Elemente nach Ziffern an dieser signifikanten Position.
Beibehalten der relativen Reihenfolge von Elementen, die denselben Schlüsselwert haben. Diese Eigenschaft der Basissortierung macht sie zu einer stabilen Sortierung.

Die letzte Iteration wird uns eine vollständig sortierte Liste liefern.

Funktionsweise des Radix-Sortieralgorithmus

Versuchen wir, die Liste der Ganzzahlen in der obigen Abbildung mit dem Radix-Sort-Algorithmus in aufsteigender Reihenfolge zu sortieren.

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

Schritt 1) Identifizieren Sie das Element mit dem Höchstwert in der Liste. In diesem Fall ist es 835.

Schritt 2) Berechnen Sie die Anzahl der Ziffern des maximalen Elements. 835 hat genau 3 Ziffern.

Schritt 3) Bestimmen Sie die Anzahl der Iterationen basierend auf Schritt 2. 835 hat 3 Ziffern, was bedeutet, dass die Anzahl der Iterationen 3 beträgt.

Schritt 4) Bestimmen Sie die Basis der Elemente. Da es sich um ein Dezimalsystem handelt, ist die Basis 10.

Schritt 5) Starten Sie die erste Iteration.

a) Erste Iteration

In der ersten Iteration betrachten wir den Einheitsstellenwert jedes Elements.

Schritt 1) Modifizieren Sie die Ganzzahl um 10, um die Einheitsstelle der Elemente zu erhalten. Beispielsweise ergibt 623 mod 10 den Wert 3 und 248 mod 10 den Wert 8.

Schritt 2) Verwenden Sie die Zählsortierung oder eine andere stabile Sortierung, um die Ganzzahlen nach ihrer niedrigstwertigen Ziffer zu organisieren. Wie aus der Abbildung hervorgeht, fallen 248 auf den 8. Eimer. 623 fällt auf den 3. Eimer und so weiter.

Nach der ersten Iteration sieht die Liste nun so aus.

Wie Sie der obigen Abbildung entnehmen können, ist die Liste noch nicht sortiert und erfordert weitere Iterationen, um vollständig sortiert zu werden.

b) Zweite Iteration

In dieser Iteration betrachten wir die Ziffer bei 10^th Platz für den Sortiervorgang.

Schritt 1) Teilen Sie die ganzen Zahlen durch 10. 248 geteilt durch 10 ergibt 24.

Schritt 2) Modifizieren Sie die Ausgabe von Schritt 1 um 10. 24 Mod 10 ergibt 4.

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

Nach der zweiten Iteration sieht die Liste nun so aus

Anhand der obigen Abbildung können Sie erkennen, dass die Liste noch nicht vollständig sortiert ist, da sie noch nicht in aufsteigender Reihenfolge vorliegt.

c) Dritte Iteration

Für die letzte Iteration möchten wir die höchstwertige Ziffer erhalten. In diesem Fall ist es die 100^thPlatz für jede der ganzen Zahlen in der Liste.

Schritt 1) Teilen Sie die ganzen Zahlen durch 100 ... 415 geteilt durch 100 ergibt 4.

Schritt 2) Modifizieren Sie das Ergebnis aus Schritt 1 um 10. 4 Mod 10 ergibt wieder 4.

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

Wie wir sehen können, ist die Liste jetzt aufsteigend sortiert. Die letzte Iteration ist abgeschlossen und der Sortiervorgang ist nun abgeschlossen.

Pseudocode des Radix-Sortieralgorithmus

Hier ist der Pseudocode für den Radix-Sort-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 j^th 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 of the elements in the j^thplace
   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 integers
  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 using 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


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Ausgang:

[162,248,415,623,835]

Komplexitätsanalyse von Radix Sort

Es müssen zwei Arten von Komplexität berücksichtigt werden: räumliche Komplexität und zeitliche Komplexität.

Speicherkomplexität: O(n+b), wobei n die Größe des Arrays und b die betrachtete Basis ist.
Zeitliche Komplexitä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 Sie sich bei der Raumkomplexität konzentrieren sollten

Anzahl der Elemente im Array, n.
Die Basis zur Darstellung der Elemente, 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 den Radixsort-Speicherplatz ineffizient machen:

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

Zeitliche Komplexität der Radixsortierung

Sie können die Zählsortierung als Unterroutine verwenden, da jede Iteration dauerte O(n+b) Zeit. Wenn Iterationen vorhanden sind, beträgt die Gesamtlaufzeit O(d*(n+b)). Dabei steht „O“ für die Komplexitätsfunktion.

Linearität der Radix-Sortierung

Radix-Sortierung ist linear, wenn

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

Vergleiche von Radix Sort mit anderen Vergleichsalgorithmen

Wie wir gesehen haben, basiert die Komplexität der Radix-Sortierung auf der Größe eines Wortes oder einer Zahl. Sie weist im durchschnittlichen und im besten Fall dieselbe Komplexität auf. Und zwar O(d*(n+b)). Außerdem unterscheidet sie sich je nach der Sortiertechnik, die Sie in der Mitte verwenden. Beispielsweise können Sie für den Zwischensortierungsalgorithmus innerhalb der Radix-Sortierung Countingsort oder Quicksort verwenden.

Anwendungen des Radix-Sort-Algorithmus

Wichtige Anwendungen von Radix Sort sind:

Radix Sort kann als Ortungsalgorithmus verwendet werden, wenn große Wertebereiche verwendet werden.
Es wird beim Aufbau eines Suffix-Arrays im DC3-Algorithmus verwendet.
Es wird in einer sequentiellen Maschine mit wahlfreiem Zugriff verwendet, die in einem typischen Computer vorhanden ist, in dem Datensätze eingegeben werden.

Du magst vielleicht: