Tag Archives: counting sort

Zählsortierung – Zählsortieralgorithmus. Bezüglich? Ja! Einfach so!

Der Algorithmus umfasst mindestens zwei Arrays, das erste – Liste der zu sortierenden Ganzzahlen, zweite – ein Array der Größe = (maximale Anzahl – minimale Anzahl) + 1, das zunächst nur Nullen enthält. Als nächstes werden die Zahlen aus dem ersten Array aussortiert und das Zahlenelement wird verwendet, um einen Index im zweiten Array zu erhalten, der um eins erhöht wird. Nachdem wir die gesamte Liste durchgegangen sind, erhalten wir ein vollständig gefülltes zweites Array mit der Anzahl der Wiederholungen der Zahlen aus dem ersten. Der Algorithmus hat einen erheblichen Overhead – Das zweite Array enthält auch Nullen für Zahlen, die nicht in der ersten Liste enthalten sind, die sogenannten. Overhead aus dem Speicher

Nachdem wir das zweite Array erhalten haben, durchlaufen wir es und schreiben die nach Index sortierte Version der Zahl, wobei wir den Zähler auf Null dekrementieren. Ein Nullzähler wird zunächst ignoriert.

Ein Beispiel für den nicht optimierten Betrieb des Zählsortieralgorithmus:

1. Eingabearray 1,9,1,4,6,4,4
2. Dann ist das zu zählende Array 0,1,2,3,4,5,6,7,8,9 (Mindestzahl 0, Höchstzahl 9)
3. Mit Gesamtzählern 0,2,0,0,3,0,1,0,0,1
4. Gesamt sortiertes Array 1,1,4,4,4,6,9

Algorithmuscode in Python 3:

numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)