Question 1

Was ist Counting Sort und wie funktioniert dieser Algorithmus?

Accepted Answer

Counting Sort ist ein nicht-vergleichsbasierter Sortieralgorithmus, der die Häufigkeit jedes Elements zählt. Er erstellt ein Hilfsarray, das die Anzahl der Vorkommen jedes Wertes speichert, und nutzt diese Information zur direkten Platzierung der Elemente in der sortierten Reihenfolge.

Question 2

Welche Zeitkomplexität hat Counting Sort?

Accepted Answer

Counting Sort hat eine lineare Zeitkomplexität von O(n + k), wobei n die Anzahl der Elemente und k der Wertebereich ist. Dies macht ihn sehr effizient, wenn der Wertebereich begrenzt ist.

Question 3

Wann sollte man Counting Sort verwenden?

Accepted Answer

Counting Sort eignet sich am besten für Daten mit einem bekannten, begrenzten Wertebereich, wie Ganzzahlen oder Zeichen. Er ist besonders effizient, wenn der Wertebereich nicht viel größer als die Anzahl der zu sortierenden Elemente ist.

Question 4

Was sind die Nachteile von Counting Sort?

Accepted Answer

Der Hauptnachteil ist der hohe Speicherverbrauch von O(k) für das Zählarray. Außerdem funktioniert er nur mit nicht-negativen Ganzzahlen oder Daten, die sich leicht auf solche abbilden lassen.

Question 5

Ist Counting Sort ein stabiler Sortieralgorithmus?

Accepted Answer

Ja, Counting Sort kann als stabiler Algorithmus implementiert werden, der die relative Reihenfolge gleicher Elemente beibehält. Dies wird durch das Rückwärtsdurchlaufen des ursprünglichen Arrays beim Platzieren der Elemente erreicht.

Counting Sort erklärt: Effizienter Sortieralgorithmus

Lernkarten zu Sortieralgorithmen: Counting Sort