Algorithmensammlung: Sortierverfahren: Countingsort

Countingsort

Countingsort ist ein Sortieralgorithmus, dessen Laufzeit linear ist. Zur Funktionsweise siehe Countingsort.

Implementierungen

Haskell

import qualified Data.Array as A
import Data.List (foldl1')

countingSort :: A.Ix a => [a] -> [a]
countingSort xs = enumerate . buildArray $ xs where
	enumerate = concatMap (uncurry (flip replicate)) . A.assocs
	buildArray = A.accumArray (+) 0 (mn, mx) . (`zip` [1,1..])
	mn = foldl1' min xs
	mx = foldl1' max xs

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;
}

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