Count Sort

Count Sort ist ein in Linearzeit laufender stabiler Sortieralgorithmus, der mit dem Prinzip “Sortieren durch Zählen” arbeitet.

Idee

• Bestimmung von Wertemenge
• Anlegen eines “Zählarrays” mit Größe der Wertemenge
• Vorkommen zählen: Iterieren durch Eingabearray
  • Jedes Element erhöht den Wert im Zählarray an der Position seines Wertes um 1
• Zurückschreiben: Iterieren durch Zählarray
  • Für jedes Element seine Position so oft zurückschreiben wie viel Wert es ist.

Implementierung

# Minimum und Maximum berechnen
 
minValue=array[0]
maxValue=array[0]
 
for element in array:
	minValue = min(minValue, element)
	maxValue = max(maxValue, element)
 
# Zählarray erstellen und initialisieren
 
countArray={}
 
for i in range(minValue, maxValue+1):
	countArray[i]=0
 
# Vorkommen zählen
 
for element in array:
	countArray[element]+=1
 
# Zurückschreiben
 
result = {}
index = 0
 
for key, value in countArray:
	while value > 0:
		result[index] = key
		value -= 1
 
return result

Kumulatives Count Sort

Im Gegensatz zum normalen Ansatz von Count Sort mit Laufzeit , erzielt das kumulative Count Sort eine Laufzeitverbesserung auf :

• Nachdem die Elemente gezählt wurden, werden die Elemente akkumuliert. Das heißt, zu jedem Wert wird die Summe seiner Vorgänger addiert. Beispiel:

Zahl	1	2	3	4	5	6
Anzahl	0	1	0	2	3	1
Akkumuliert	0	1	1	3	6	7

Im Code kann dieser Teil mittels einer for-Schleife umgesetzt werden:

index = minValue
 
while index < len(countArray):
	countArray[index+1] += countArray[index]
	index += 1

• Jetzt steht an jeder Stelle die letzte Position, an der die Zahl vorkommt. Beispiel: countArray[3] beinhaltet jetzt die letzte Position, an der die Ziffer 3 vorkommt.
• Das machen wir uns zu Nutze: Wir erstellen ein resultArray, wo wir jetzt die Werte reinschreiben.
• Wir iterieren jetzt über das Eingabearray (nicht über das countArray, hier wird die Laufzeit eingespart!)
• Jede Zahl wird an die Position geschrieben, die im countArray ist. Danach wird der Wert des countArray um 1 verringert.

for element in inputArray:
	result[countArray[element]-1] = element
	countArray[element] -= 1

Kumulatives Count Sort verbessert die Laufzeit um .

Laufzeit

Bei einem Wertebereich von ist die Laufzeit von Count Sort