Radix-Sortierung

1. Radix-Sortieralgorithmus
2. Radix-Sortierbeispiel
3. Implementierung des Radix-Sortieralgorithmus
4. Radix-Sortieralgorithmus Komplexität

Radix sort ist ein nicht-komparativer Sortieralgorithmus. Dieser Algorithmus vermeidet Vergleiche, indem er Elemente entsprechend der Radix (Radix/Base ist die Anzahl der eindeutigen Ziffern, die zur Darstellung von Zahlen verwendet werden) in Buckets einfügt. Dezimalzahlen haben z. B. zehn eindeutige Ziffern). Es sortiert Elemente basierend auf den Ziffern der einzelnen Elemente. Es führt eine Zählsortierung der Ziffern von der niedrigstwertigen Ziffer bis zur höchstwertigen Ziffer durch. Sie wird auch als Bucket-Sort oder digitale Sortierung bezeichnet und ist auf Parallelmaschinen sehr nützlich.

Radix-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

Radix-Sortierbeispiel

Angenommen, wir haben das Array: (1851, 913, 1214, 312, 111, 23, 41, 9). Wir werden es mit dem Radix-Sortieralgorithmus sortieren.

In der ersten Iteration sortieren wir nach der Einerstelle und bewegen uns dann zur Zehner-, Hunderter- und Tausenderstelle, um das endgültige sortierte Array als 9, 23, 41, 111, 312, 913, 1214, 1851 zu erhalten.

Implementierung des Radix-Sortieralgorithmus

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

void countingSort(int arr[], int n, int place) {
  int output[n];
  int count[N];

  for (int i = 0; i < N; ++i) count[i] = 0;

  for (int i = 0; i < n; i++) count[(arr[i] / place) % 10]++;

  for (int i = 1; i < N; i++) count[i] += count[i - 1];

  for (int i = n - 1; i >= 0; i--) {
    output[count[(arr[i] / place) % 10] - 1] = arr[i];
    count[(arr[i] / place) % 10]--;
  }

  for (int i = 0; i < n; i++) arr[i] = output[i];
}

void radixsort(int arr[], int n) {
  int max = maxm(arr, n);
  for (int place = 1; max / place > 0; place *= 10) countingSort(arr, n, place);
}

int main() {
  int n = 5;
  int arr[5] = {1851, 913, 1214, 312, 111};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  radixsort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Radix-Sortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Radixsort hat eine Zeitkomplexität von O(n + b), wobei b der Bereich der Eingabe ist. Wenn es d Ziffern im maximalen Element maxm gibt, dann wird die Zeitkomplexität von Radix Sort O(d*(n + b)). Da d und b normalerweise klein sind, liegt die Zeitkomplexität in der Größenordnung von [Big Theta]: O(n).

• Schlimmster Fall

Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(n).

• Bester Fall

Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n). Sie ist identisch mit der Zeitkomplexität im schlimmsten Fall.

Raumkomplexität

Die Raumkomplexität für den Radix-Sortieralgorithmus ist O(n+b), wobei b der Bereich der Eingabe ist. Sie ergibt sich aus den Arrays count & output in der Radixsort. Manchmal kann b größer als n sein, so dass die Komplexität nicht linear ist.