Definition

Counting Sort ist ein nicht-vergleichsbasierter Sortieralgorithmus, der besonders effizient bei ganzen Zahlen mit kleinem Wertebereich ist. Er zählt, wie oft jedes Element vorkommt, berechnet daraus die Position und erstellt so ein sortiertes Array. Die Laufzeit beträgt O(n + k), wobei n die Anzahl der Elemente und k der Wertebereich ist.

Coutingsort PHP-Skript

Das folgende PHP-Skript zeigt die Funktionsweise von Counting Sort mit Syntax-Highlighting:


<?php
function countingsort($arr) {
    // Abbruch, wenn sich im Array ein nicht ganzzahliges oder negatives Element befindet
    foreach ($arr as $v) {
        if (!is_int($v) || $v < 0) {
            return false;
        }
    }

    // Höchsten Zahlenwert im Array ermitteln
    $max = max($arr);

    // Leeres Zählarray erstellen und mit Nullen füllen
    $count = array_fill(0, $max + 1, 0);

    // Zählvorgang: Für jede Zahl im Ursprungsarray Zähler erhöhen
    foreach ($arr as $value) {
        $count[$value]++;
    }

    // Sortiertes Array erstellen
    $sort = [];

    // Zahlen entsprechend ihrer Häufigkeit ins sortierte Array einfügen
    for ($i = 0; $i <= $max; $i++) {
        while ($count[$i] > 0) {
            $sort[] = $i;
            $count[$i]--;
        }
    }

    // Sortiertes Array zurückgeben
    return $sort;
}

// Beispielarray
$array = [9, 3, 5, 1, 0, 3, 7, 23];

// Sortierung aufrufen
$sortiert = countingsort($array);

// Ausgabe
if (is_array($sortiert)) {
    print_r($sortiert);
} else {
    echo "Sortierung fehlgeschlagen. Das Array darf keine negativen Zahlen und nur Ganzzahlen enthalten.";
}
?>

Allgemeine Erklärung von Counting Sort

Counting Sort ist ein einfacher, aber sehr effizienter Sortieralgorithmus für ganzzahlige Werte. Er funktioniert nicht wie andere Sortieralgorithmen durch Vergleiche, sondern indem er zählt, wie oft jede Zahl im Eingabearray vorkommt.

Wie funktioniert Counting Sort?

Alle Zahlen im Eingabearray müssen nicht-negativ und ganzzahlig sein.
Ein Hilfsarray (Zählarray) zählt, wie oft jede Zahl vorkommt.
Danach wird das Ergebnisarray zusammengesetzt, indem die Zahlen entsprechend ihrer Häufigkeit wiederholt eingefügt werden.

Counting Sort ist besonders nützlich, wenn man eine große Anzahl von Werten mit kleinem Wertebereich sortieren möchte, z. B. Noten, Alter oder Punkte. Der Algorithmus ist in der Regel schneller als vergleichsbasierte Sortierverfahren wie Bubble Sort oder Insertion Sort, hat aber Einschränkungen bei Gleitkommazahlen oder sehr großen Wertebereichen.

Vorteile & Nachteile von Counting Sort

Vorteile:

Sehr schnelle Laufzeit bei beschränktem Wertebereich: O(n + k)
Stabiler Sortieralgorithmus (Reihenfolge gleicher Elemente bleibt erhalten)
Kein Vergleichen notwendig (kein Vergleichssortieren)
Ideal für große Datenmengen mit kleinem Wertebereich
Einfach zu implementieren

Nachteile:

Nur für ganzzahlige Werte geeignet
Unpraktisch bei sehr großem Wertebereich (hoher Speicherbedarf)
Funktioniert ohne Anpassung nicht mit negativen Zahlen oder Fließkommazahlen
Kein In-Place-Sortieren (benötigt zusätzlichen Speicher für Zählarray und Ausgabe)

Kurz und Knapp - Ablauf auf einem Blick

Eingabe: Array von Ganzzahlen
Maximalen Wert finden
Zählarray erstellen
Häufigkeiten zählen
(Kumulative Summe bilden)
Elemente sortiert einsortieren
Sortiertes Array ausgeben

Effizienz & Laufzeit von Counting Sort

Komplexität:
- Best Case: O(n + k)
- Average Case: O(n + k)
- Worst Case: O(n + k)
Dabei ist:
n = Anzahl der Elemente im Eingabearray
k = Wertebereich (z. B. max - min)
Stabilität: Ja, Counting Sort ist stabil (gleiche Werte behalten ihre Reihenfolge).
Speicherverbrauch: Zusätzlicher Speicher wird benötigt für das Zählarray (Größe = k).
Voraussetzung: Funktioniert nur sinnvoll bei ganzzahligen Werten in einem begrenzten Bereich.
Besonders geeignet für:
- große Datenmengen mit kleinem Wertebereich
- nicht-negative oder verschiebbar negative Ganzzahlen
- Vorsortierung oder vorberechnete Histogramme

Prüfe dich selbst!

Interaktive Aufgaben: Aufgaben folgen!

Counting Sort zählt, wie oft jedes Element vorkommt und nutzt diese Häufigkeiten, um die Positionen im Ergebnisarray zu bestimmen.

Erstelle ein Zählarray: [0, 0, 2, 1, 1]
Kumulieren: [0, 0, 2, 3, 4]
Sortiert: [2, 2, 3, 4]

Das solltest du dir merken!

Wichtige Infos zu Counting Sort

Counting Sort ist ein nicht-vergleichender Sortieralgorithmus für ganzzahlige Werte.
Er zählt die Häufigkeit jedes Werts und berechnet daraus die Positionen im sortierten Array.
Effizient bei kleinem Wertebereich und großer Anzahl an Elementen (Laufzeit: O(n + k), n = Elemente, k = Wertebereich).
Wichtig: Counting Sort funktioniert nur mit nicht-negativen Ganzzahlen.
Negative Werte können nicht direkt sortiert werden, da der Algorithmus Indizes im Zählarray verwendet, die nicht negativ sein können.
Für negative Werte muss man den Wertebereich verschieben (z. B. alle Werte um den Betrag des kleinsten negativen Werts erhöhen).

Unterstützung von Negativen Zahlen

Das folgende PHP-Skript zeigt die Funktionsweise von Counting Sort mit Syntax-Highlighting: Damit der Countingsort-Algorithmus negative Zahlen untersützt, muss das Array „verschoben“ werden. Das Zählarray $count wird somit nicht mehr von 0 bis zum Maximalwert aufgebaut, sondern vom Minimalwert bis zum Maximalwert.


<?php
function countingsort($arr) {
    // Abbruch: Wenn ein Element keine ganze Zahl ist
    foreach ($arr as $v) {
        if (!is_int($v)) {
            return false;
        }
    }

    // Höchsten und niedrigsten Wert im Array finden
    $max = max($arr);
    $min = min($arr);

    // Spanne (Abstand zwischen min und max)
    $span = abs($max - $min);

    // Leeres Zählarray initialisieren
    $count = array_fill(0, $span + 1, 0);

    // Zählen: Häufigkeit jeder Zahl erfassen
    foreach ($arr as $value) {
        $count[$value - $min]++;
    }

    // Sortiertes Array erstellen
    $sort = [];

    for ($i = 0; $i < count($count); $i++) {
        while ($count[$i] > 0) {
            $sort[] = $i + $min;
            $count[$i]--;
        }
    }

    // Ergebnis zurückgeben
    return $sort;
}

// Beispielarray
$array = [9, 3, -4, 1, -43, 3, 7, 23];

// Sortierung aufrufen und ausgeben
$sortiert = countingsort($array);

if (is_array($sortiert)) {
    print_r($sortiert);
} else {
    echo "Sortierung fehlgeschlagen. Das Array darf nur Ganzzahlen enthalten.";
}

?>

Erklärung – Wie funktioniert das? Und wie werden negative Zahlen berücksichtigt?

Counting Sort funktioniert normalerweise nur mit nicht-negativen ganzzahligen Werten, da das Zählarray die Werte direkt als Index verwendet. Um negative Zahlen zu unterstützen, wird ein Offset eingebaut:

Schritt-für-Schritt:

Prüfen auf Ganzzahlen:
Der Code durchläuft alle Werte im Array und bricht ab, wenn ein Wert kein Integer ist (z. B. Float oder String).
Minimal- und Maximalwert bestimmen:
min($arr) und max($arr) finden den Wertebereich (inkl. negativer Werte).
Zählarray anlegen:
Normalerweise wäre das Zählarray so groß wie der größte Wert. Hier wird es auf die Spanne ($span) zwischen min und max ausgelegt.
Offset verwenden:
Weil negative Zahlen keine gültigen Array-Indizes sind, wird jeder Wert um -$min verschoben.

Beispiel: Bei einem Wert von -43 und einem min = -43, wird $count[-43 - (-43)] = $count[0] erhöht.
Sortiertes Array aufbauen:
Die Werte werden entsprechend ihrer Häufigkeit in aufsteigender Reihenfolge wieder zusammengesetzt, wobei der Offset ($i + $min) zurückgerechnet wird.
Ausgabe:
Das fertige sortierte Array wird ausgegeben. Bei ungültigen Werten wird eine Fehlermeldung angezeigt.

Anmerkung zur Laufzeit: Die Laufzeit für die negative Unterstützung ändert sich nun zu O(n + ($max-$min)).

Counting Sort in PHP - Workshop