Countingsort

Countingsort

Countingsort (von engl. count „zählen“) ist ein einfaches, stabiles Sortierverfahren. Es sortiert eine gegebene Zahlenfolge nicht durch Vergleiche, sondern setzt das Wissen voraus, aus welchem Intervall die Zahlen des Schlüssels stammen.

Inhaltsverzeichnis

Problemstellung

Die zu sortierenden Zahlen liegen in \{0,1,\ldots,k\} für ein festes, im Voraus bekanntes k. Dann bestimme für jedes zu sortierende Element x die Anzahl der Elemente, welche in der sortierten Reihenfolge vor x liegen, und platziere damit x an die korrekte Stelle.

Eingabe

Feld A[1..n] mit A[j] \in \{0, \ldots, k\} für alle j=1,\ldots,n. Als Parameter werden A,k,n übergeben.

Ausgabe

Feld B[1..n] mit Inhalt von A in sortierter Reihenfolge.

Zudem wird bei dem Sortierverfahren ein Hilfsvektor C[0..k] benötigt.

Implementierungen

Pseudocode

Der nachfolgende Pseudocode bezieht sich auf die in der Problemstellung benutzten Bezeichnungen.

COUNTINGSORT(A, B, k)
1 for i = 0 to k
2     do C[i] = 0
3 for j = 1 to length[A]
4     do C[A[j]] = C[A[j]] + 1
          //C[i] gibt nun an, wie oft i in A vorkommt.
5 for i = 1 to k
6     do C[i] = C[i] + C[i - 1]
          //C[i] gibt nun die Anzahl der Elemente <= i in A an,
          //bzw. die Stelle mit dem größten Index, an dem
          //das Element i im sortierten Array stehen wird.
7 for j = length[A] downto 1
8     do B[C[A[j]]] = A[j]
9         C[A[j]] = C[A[j]] - 1

Python

def counting_sort(A):
    C = [0] * (max(A)+1)
    B = [""] * len(A)
    for index in xrange(len(A)):
        C[A[index]]+=1
    for index in xrange(1, len(C)):
        C[index]+=C[index-1]
    for index in xrange(len(A)-1, -1, -1):
        B[C[A[index]]-1]=A[index]
        C[A[index]]-=1
    return B

Java

// sortiert ein Zahlen-Array mit CountingSort
// erwartet als Parameter ein int-Array und gibt dieses sortiert wieder zurück
static int[] countingSort(int[] numbers) {
        // Maximum der Zahlen berechnen
        int max = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
                // wenn es größeres als das aktuelle gibt, ist das nun das neue größte
                if (numbers[i] > max)
                        max = numbers[i];
        }
 
        // temporäres Array erzeugen mit: Länge = Maximum des Zahlenarrays + die "0"
        int[] sortedNumbers = new int[max+1];
 
        // Indizes des Zahlen-Arrays durchgehen
        for (int i = 0; i < numbers.length; i++) {
                // wir zählen, wie oft jede Zahl aus numbers vorkommt und
                // speichern diese Anzahl in sortedNumbers[] bei Index number[i]
                sortedNumbers[numbers[i]]++;
        }
 
        // insertPosition steht für die Schreib-Position im Ausgabe-Array
        int insertPosition = 0;
 
        // Indizes von sortedNumbers[] durchgehen, um zu sehen, wie oft jede Zahl vorkommt
        for (int i = 0; i <= max; i++) {
                // Anzahl von i durchgehen, um gleiche Zahlen hintereinander einzutragen
                for (int j = 0; j < sortedNumbers[i]; j++) {
                        // das Zahlen-Array wird jetzt sortiert neu geschrieben für jedes
                        // Auftreten von i
                        numbers[insertPosition] = i;
                        insertPosition++;
                }
        }
        return numbers;
}

Beispiel

Ausführung von Countingsort auf ein Eingabefeld A[1..8] mit Elementen aus \{0, \ldots, 5\} mit Hilfsfeld C und sortierter Ausgabe in Feld B.

1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
0 1 2 3 4 5
0 0 0 0 0 0
1 2 3 4 5 6 7 8
               

Darstellung untereinander Ausgangsliste A, Hilfsvektor C, dessen Länge vom Definitionsbereich der Liste abhängt. In unterster Liste werden die Elemente sortiert eingefügt. Die Obige Abbildung stellt die gegebene Zahlenfolge dar, wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde, indem lediglich der Vektor C mit 0 initialisiert wird. Zweite Schleife inkrementiert für jede Ziffer deren Stelle im Vektor um eins.

1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
0 1 2 3 4 5
2 0 2 3 0 1
1 2 3 4 5 6 7 8
               

Die dritte Schleife summiert den Vektor C auf, so dass dessen Inhalt angibt, bis zu welcher Position ein Wert in der sortierten Liste auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, dass die letzte der beiden Zahlen in der Folge überhaupt nicht auftaucht, also vorher in C an dieser Position ein 0 gewesen war.

1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
0 1 2 3 4 5
2 2 4 7 7 8
1 2 3 4 5 6 7 8
               

Nun folgt die letzte Schleife. In dieser werden nun sukzessive die Werte aus A in den Vektor B übertragen und zwar genau an der Stelle im Zielvektor, die der Hilfsvektor C für die entsprechende Zahl angibt. Vor der Schleife ist dies immer die letzte Stelle, an der die Zahl auftauchen wird. Nach dem übertragen jeder Zahl wird zusätzlich der Wert in C[Zahl] dekrementiert. Die nächste gleiche Zahl wird deswegen eine Stelle weiter vorn im Zielvektor eingefügt. Nachfolgend die 8 Schritte.

8. Schritt

1 2 3 4 5 6 7 8
2 5 3 0 2 3 0 3
0 1 2 3 4 5
0 2 2 4 7 7
1 2 3 4 5 6 7 8
0 0 2 2 3 3 3 5

Laufzeitanalyse

Wie man aus obigem Pseudocode leicht ersehen kann, hängt die Laufzeit der Funktion von N (Anzahl der Elemente des Eingabe(arrays)) und M(Anzahl jeder Zahl) ab. Die erste for-Schleife wird genau N-mal durchlaufen, die zweite genau M-mal. Die Zeitkomplexität von Countingsort beträgt \mathcal{O}(N + M).

Speicherplatzbedarf

Zusätzlich zur Eingabe, die N Speicherfelder benötigt, wird noch eine Liste zur Speicherung der Häufigkeiten der Zahlenwerte benötigt. Diese benötigt im Falle der obigen Implementierung einen Speicherplatz von M Feldern. Die Platzkomplexität von Countingsort liegt in \mathcal{O}(N + M).

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в)… …   Википедия

  • Distributionsort — Radixsort (von lat. Wurzel, Basis) oder auch Distributionsort (von engl. Distribution – „Verteilung“), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out of place arbeitet und auf Countingsort basiert. Das… …   Deutsch Wikipedia

  • Fachverteilen — Radixsort (von lat. Wurzel, Basis) oder auch Distributionsort (von engl. Distribution – „Verteilung“), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out of place arbeitet und auf Countingsort basiert. Das… …   Deutsch Wikipedia

  • Fachverteilung — Radixsort (von lat. Wurzel, Basis) oder auch Distributionsort (von engl. Distribution – „Verteilung“), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out of place arbeitet und auf Countingsort basiert. Das… …   Deutsch Wikipedia

  • Radix sort — Radixsort (von lat. Wurzel, Basis) oder auch Distributionsort (von engl. Distribution – „Verteilung“), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out of place arbeitet und auf Countingsort basiert. Das… …   Deutsch Wikipedia

  • Sortieralgorithmen — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Sortieralgorithmus — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Stabil (Sortierverfahren) — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

  • Stabiles Sortierverfahren — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”