Countingsort

2013-09-15
 Sortierung

Countingsort (Sortierung durch Zählung) ist eine Sortierungsmethode, die ohne Vergleiche funktioniert. Sie kann je nach zu sortierendem Typen und sehr viel schneller sein als Mergesort sein. Es ist aber in der normalem Implementation nötig ein Eingangs-, ein Ausgangsfeld sowie ein Hilfsfeld zu erstellen. Der Algorithmus ist besonders effektiv bei kleinen Wertebereichen der Eingangswerte, im Verhältnis zur Eingangsfeldgröße. Er funktioniert normalerweise nur mit Ganzzahlwerten, kann aber auch für andere Typen mit einer entsprechenden Transformation der Daten benutzt werden. Dieses wird näher beim Radixsort erläutert.

Beispiel (Quellcode): countingsort.cpp
Download (Quellcode): countingsort.zip

Häufigkeitsaufnahme

Zu Beginn wird ein Zählfeld erstellt, welches die Größe des erwarteten Wertebereiches besitzt. Die Zähler werden mit Null initialisiert. Nun wird der entsprechende Zähler, mit dem Index des Eingangswertes, im Zählfeld erhöht. Kurz gesagt, die Häufigkeitsverteilung wird aufgenommen.

Da dieses Zählfeld, den Wertebereich komplett darstellt, ist die Reihenfolge und Anzahl der Werte jetzt schon bekannt. Im einfachsten Falle braucht nun nur jeder Wert mit der entsprechenden Anzahl in das Ausgabefeld geschrieben werden. Meist werden jedoch, nur Schlüsselwerte verwendet, die nicht das Objekt darstellen, daher reicht es nicht den Schlüsselwert auszugeben, sondern die entsprechenden Objekte müssen mitkopiert werden. Hierzu wird eine Indexliste erstellt, die angibt ab welcher Position welcher Schlüsselwert im Ausgabefeld steht.

Feldumverteilung durch Countingsort

Ausgabe

Nun werden, die Schlüsselwerte aus dem Eingangsfeld ein zweites Mal eingelesen und entsprechend ihres Indexes in der Indexliste in die Ausgabeliste geschrieben. Bei mehreren gleichen Schlüsselwerten, wird der entsprechende Index in der Indexliste, erhöht.

Durch den Beispielcode

Der Beispielcode, enthält eine Templateklasse (C++), die sich nur für Ganzzahlwerte eignet:

  • die Sortierungsfunktion

    const std::vector<_TYPE>& Sort(const std::vector<_TYPE>& toSort, _TYPE nMin, _TYPE nMax)
    18

    Die Eingangsparameter sind das Feld, welches sortiert werden soll, sowie das Minimum und Maximum des Wertebereichs. Das Ausgabefeld wird automatisch erstellt.

Codeanmerkungen

  1. Der Code erzeugt ein Hilfsfeld mit

    std::vector<size_t> histogram(nMax-nMin+1);
    21

    wobei dieses nur den Wertebereich aufnimmt.

  2. Der Beispielcode kann nur mit Ganzzahltypen verwendet werden, da keine Transformation für andere Datentypen, sofern möglich, definiert ist.

  3. Die ersten beiden Aufrufparameter des Programms definieren den Wertebereich.

  4. Die Ausrufparameter des Programms werden als sortierende Elemente benutzt:

    std::vector<std::string> arrayToSort;
for(int n=3; n<argc; n++)
   arrayToSort.push_back(atoi(argv[n]));
    78
79
80

    So ergibt

    ./countingsort -2 10 8 7 6 5 4 3 2 4 5 6 -1 -2

    die Ausgabe

    Counting sort test...

 sorted 12 elements:
     1. -2
     2. -1
     3. 2
     4. 3
     5. 4
     6. 4
     7. 5
     8. 5
     9. 6
    10. 6
    11. 7
    12. 8