Counting Sort: Visualisierung und Pseudocode

Beobachte, wie Häufigkeiten gezählt, kumuliert und schließlich verwendet werden, um das Ausgabearray stabil zu füllen. Die aktuell ausgeführte Pseudocode-Zeile ist rechts hervorgehoben.

Array:

1. Eingabearray A

Erst von links nach rechts zählen, später für die stabile Ausgabe von rechts nach links lesen.

2. Zählarray C

3. Ausgabearray B

B wird mithilfe der kumulierten Häufigkeiten gefüllt.

Pseudocode

Bei jedem Schritt wird die zugehörige Zeile markiert. Die Variablen darunter zeigen den aktuellen Zustand.

          01
          minimum ← min(A); maximum ← max(A)
        
          02
          C[0 … maximum−minimum] ← 0
        
          03
          B[0 … n−1] ← leer
        
          04
          für i ← 0 bis n−1:
        
          05
              C[A[i]−minimum] ← C[A[i]−minimum] + 1
        
          06
          für j ← 1 bis maximum−minimum:
        
          07
              C[j] ← C[j] + C[j−1]
        
          08
          für i ← n−1 bis 0, rückwärts:
        
          09
              v ← A[i]
        
          10
              pos ← C[v−minimum] − 1
        
          11
              B[pos] ← v
        
          12
              C[v−minimum] ← C[v−minimum] − 1
        
          13
          gib B zurück

Tempo: ms

gelesen gezählt / kumuliert gerade verändert in B abgelegt

Negative Zahlen: Der Wert v wird im Zählarray unter dem Index v − minimum gespeichert.
Laufzeit: O(n + k), wobei k = maximum − minimum + 1.
Stabilität: Das Eingabearray wird beim Einfügen in B von rechts nach links durchlaufen.

Counting Sort: Visualisierung und Pseudocode

1. Eingabearray A

2. Zählarray C

3. Ausgabearray B

Ablauf / Protokoll