Sortierverfahren: Countingsort

Countingsort ist ein Sortierverfahren, das sehr effizient auf einen beschränkten Intervall große Datenmengen sortieren kann. Es wurde 1954 von Harold H. Seward entickelt. Countingsort ist eines der wenigen Sortierverfahren welches nicht vergleichsbasiert arbeitet, sondern die Vorkommnisse der einzelnen Werte des Intervals zählt. Es ist daher wichtig, dass das Interval einen kleinen Wertebereich aufweist. Praktisch gesehen eignen sich Zahlen welche sich in einen Histogramm darstellen lassen wie beispielsweise Jahreszahlen, ein Alter oder ein Gewicht in Kg.

Der Algorithmus glieder sich in drei Schritte: Zuerst wird jedes Element des Intervals einzeln durchgegangen und ein Histogramm daraus erstellt. Das Histogram repräsentiert wie oft ein bestimmter Wert des Intervals in der zu sortierenden Menge vorkommt.

Aus diesem Histogram wird anschließend die kumulierte Häufigkeit berechnet. Dazu addiert man, beginnend von dem ersten Element, die Werte des Histograms bis zu dem Wert, für den man die kumulierte Häufigkeit berechnen möchte.

(1)  

Zuletzt wird ein neues Array mit den zu sortierenden Werten gefüllt. Dazu wird der Funktionswert der kumulierten Häufigkeit an der Stelle des Wertes des Intervalls gelesen .  Nachdem dies geschehen ist, muss der Wert der kumulierten Häufigkeit an dieser Stelle um einen Wert verkleinert werden damit das nächste Element mit diesem Wert nicht an die gleiche Position ein zweites Mal gesetzt wird. Das ganze lässt sich prima in einem Beispiel verdeutlichen.

In dem Oben gezeigten Beispiel sollen neun Würfel (6,4,3,2,2,1,3,6,2) nach ihrer Augenzahl geordnet werden. Zuerst wird aus den Augenzahlen ein Histogram erstellt. Das Interval liegt bei Würfeln zwischen 1-6. Die 1 wurde einmal gewürfelt. Der Wert des Histograms an der Stelle 1 ist deswegen ebenfalls 1. Die 2 kommt insgesamt drei mal vor und erhält daher die 3 als Funktionswert. Dies wird so lange fortgeführt bis alle Werte des Intervals betrachtet wurden.

Im Anschluss wird die kumulierte Häufigkeit berechnet. Die Stelle 1 erhält den Funktionswert 1, da das Histogramm bei 1 auch nur 1 ist. Der Funktionswert der kumulierten Häufigkeit von 2 ist 4, da nun der Funktionswert des Histograms von 1 und 2 summiert werden muss.

Ist die kumulierte Häufigkeit für jeden Wert bekannt kann das Ergebnis berechnet werden. Dazu werden nun die Würfel noch einmal durchgegangen und an die Stelle im Ergebnis einsortiert, die dem Funktionswert der kumulierten Häufigkeit entsprechen.

In unserem Beispiel hat der erste Würfel die Augenzahl 6. Im Histogram ist der Funktionswert für 6 die 9. An diese Stelle wird daher der Würfel einsortiert.

(x,x,x,x,x,x,x,x,6)

Wichtig dabei ist, dass der Funktionswert der kumulierten Häufigkeit an dieser Stelle um eine Stelle vermindert werden muss. Aus der 9 wird also 8.

Der Nächste Würfel hat die Augenzahl 4 und den Funktionswert 7. Er wird also an die siebten Stelle einsortiert.

(x,x,x,x,x,x,4,x,6)

Dieser Vorgang wird fortgesetzt bis jeder Würfel einsortiert ist. Damit ist die Sortierung beendet.

public static <T> void sort(T[] source, T[] result, Function<T, Integer> indexer, int maxIndices) {
	Integer[] hist = new Integer[maxIndices];
	for (int i = 0; i < hist.length; i++) {
		hist[i] = Integer.valueOf(0);
	}
	
	for (int i = 0; i < source.length; i++) {
		hist[indexer.apply(source[i])]++;
	}
	
	for (int i = 1; i < hist.length; i++) {
		hist[i] = hist[i] + hist[i-1];
	}
	
	for (int i = 0; i < source.length; i++) {
		final int index = indexer.apply(source[i]);
		result[hist[index] - 1] = source[i];
		hist[index]--;
	}
}

Komplexität