Zählende Sortierung

Zählende Sortierung ist ein nicht-vergleichender Sortieralgorithmus. Er sortiert ein Array, indem er das Vorkommen jedes eindeutigen Elements zählt. Die Anzahl der eindeutigen Elemente wird teilweise gehasht und dann werden Berechnungen durchgeführt, um den Index jedes Elements im endgültigen, sortierten Array zu finden. Es ist ein recht schneller Algorithmus, der aber für große Datensätze ungeeignet ist. Er wird als Unterprogramm innerhalb von radix sort verwendet.

Zählender Sortieralgorithmus

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

Zählende Sortierung Beispiel

Angenommen, wir haben das Array: (6, 3, 2, 7, 4, 5, 4, 2). Wir werden es mit dem Zählsortieralgorithmus sortieren.

• maxm = 7
• minm = 2
• range = 6
• count und output werden mit Nullen initialisiert.

• Array count, nachdem die Anzahl aller Elemente berechnet wurde.

• Array count nach Kumulation der Summe der Elemente.

• Erste Iteration: A[7]=2

• Zweite Iteration: A[6]=4

• Dritte Iteration: A[5]=5

• Vierte Iteration: A[4]=4

• Fünfte Iteration: A[3]=7

• Sechste Iteration: A[2]=2

• Siebte Iteration: A[1]=3

• Achte Iteration: A[0]=6

Zum Schluss speichern wir das Array output in A und erhalten das sortierte Array - 2, 2, 3, 4, 4, 5, 6, 7.

Implementierung des Zählsortieralgorithmus

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

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

void countingSort(int arr[], int n) {
  int min = minm(arr, n);
  int max = maxm(arr, n);
  int range = max - min + 1;
  int count[range] = {};
  int output[n];
  for (int i = 0; i < n; i++) count[arr[i] - min]++;

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

  for (int i = n - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }

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

int main() {
  int n = 7;
  int arr[7] = {3, 5, 1, 1, 4, 2, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  countingSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Diese Implementierung funktioniert auch für negative Zahlen.

Komplexität des Zählsortieralgorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Counting Sort iteriert zweimal durch alle n Elemente und iteriert einmal durch das count-Array. Er hat also eine Zeitkomplexität von O(n + b), wobei b der Bereich der Eingabe ist. Da b oft klein ist, sagt man, dass die Zeitkomplexität der zählenden Sortierung in der Größenordnung von [Big Theta] liegt: O(n).

• Schlechtester 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 zählenden Sortieralgorithmus ist O(n+b), wobei b der Bereich der Eingabe ist. Sie ergibt sich aus den Arrays count & output. Manchmal kann b größer als n sein, aber wenn b klein ist, sagt man, dass die Zeitkomplexität von O(n) ist.