Ereignisgesteuerte Animation: Sortieren durch Auszählen
Event-driven Animation of Counting Sort - Abstract
Counting Sort is a rather simple sorting algorithm which is very efficient under certain pre-conditions. In this case study we show how Counting Sort can be animated using the technique of event-driven animation which has already been described on another subpage of this site (Ereignisgesteuerte Animation / event-driven animation).
Download
The workbook containing the entire code can be downloaded at the bottom of this subpage.
Sortieren durch Auszählen – der Algorithmus
Sortieren durch Auszählen (Counting Sort) ist eine der wenigen Sortiermethoden, welche ohne Größenvergleiche auskommen. Gewöhnlich wird es auf die Sortierung ganzer Zahlen in einem mäßig großen Wertebereich angewandt. Wir wollen zunächst vereinfachend annehmen, dass dies Zahlen im Bereich 1, 2, …, maxv sind.
Das Verfahren läuft in zwei Phasen ab:
-
Man zählt, wie oft die verschiedenen Werte
vorkommen. Hierfür geht man die zu sortierende Liste von Zahlen durch und merkt sich anhand einer Zählerliste, wie oft jeder Wert vorkommt.
- Aufbau der sortierten Liste aus dem Ergebnis der ersten Phase.
Beispiel
Für ein einfaches Beispiel wollen wir annehmen, dass die zu sortierende Liste lediglich zehn Zahlen umfasst und dass diese Zahlen im Bereich von 1 bis 4 liegen:
3, 1, 4, 3, 3, 1, 1, 2, 1, 4
Phase 1: Zählphase
Die Auszählung der Werte resultiert in der folgenden Zusammenstellung. In der oberen Zeile steht jeweils der Wert, in der unteren, wie oft er vorkommt.
|
1 |
2 |
3 |
4 |
|
4 |
1 |
3 |
2 |
Phase 2: Zusammenstellung der sortierten Liste
Der Zählerliste aus der ersten Phase entnehmen wir unmittelbar die Zusammenstellung der sortierten Liste. Um diese zu erhalten, müssen wir offensichtlich viermal die 1, einmal die 2, dreimal die 2 und zweimal die 4 ausschreiben. Damit ergibt sich als Endergebnis:
1, 1, 1, 1, 2, 3, 3, 3 , 4, 4
Eine VBA-Funktion für Counting Sort – simple Fassung
Die folgende Funktion beruht auf der Voraussetzung, dass sich die zu sortierenden ganzen Zahlen im Bereich 1, 2, …, maxv befinden.
Der Parameter a, ein Array vom Typ Integer, enthält die zu sortierenden Zahlen; die Obergrenze maxv des Wertebereichs wird ebenfalls als Parameter übergeben, muss also schon vor dem Aufruf der Funktion ermittelt worden sein.
Das Array c ist ein Array von Zählern; es entspricht der im obigen Beispiel beschriebenen Zählerliste. Seine Indizes beginnen bei 1 und laufen bis maxv, stimmen also mit den möglichen Werten des Wertebereichs überein.
Die Zählung geschieht in der ersten For-Schleife. Diese Schleife geht alle Werte a(i) nacheinander durch und schreibt jeweils den entsprechenden Zähler c(a(i)) fort.
In der darauf folgenden Doppelschleife wird dann das Zählerarray c benutzt, um die Werte in der richtigen Reihenfolge in das Zielarray s zu schreiben. Hierzu geht die äußere Schleife (i-Schleife) alle möglichen Werte von 1 bis maxv durch bzw., gleichbedeutend, alle Indizes des Zählerarrays c. Die einzelnen Zähler werden mit Hilfe der inneren Schleife (j-Schleife) abgearbeitet, welche jeden Wert i so oft in das Array s schreibt, wie es dem Zähler c(i) entspricht.
Public Function CountingSortS(ByRef a() As Integer, _
ByVal maxv As Integer) As Integer()
Dim c() As Integer 'counts
Dim s() As Integer 'sorted array (result)
ReDim c(1 To maxv)
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, z As Integer
'counting occurrences of values
For i = 1 To UBound(a)
c(a(i)) = c(a(i)) + 1
Next i
'deriving sorted array from counts
z = 0
For i = 1 To maxv
For j = 1 To c(i)
z = z + 1
s(z) = i
Next j
Next i
CountingSortS = s
End Function
Eine flexiblere Funktion für Counting Sort
Wir lassen nun die Annahme fallen, dass der Wertebereich der zu sortierenden Zahlen bei 1 beginnt und wollen nun beliebige ganze Zahlen im Integer-Bereich zulassen.
Bei der ersten Fassung der Sortierfunktion wurde der Höchstwert maxv in der zu sortierenden Liste vorher ermittelt und der Funktion als Parameter übergeben.
Wir gehen in der zweiten Fassung analog vor, müssen hier aber auch den kleinsten Wert minv vorher ermitteln und als Parameter übergeben.
Die Grundstrategie bleibt gegenüber der simplen Version unverändert. Der Hauptunterschied betrifft die Behandlung des Zählerarrays c. In der simplen Version stimmten die Indizes von c mit den Werten überein, welche im Array a vorkommen konnten. Wenn wir auch in der zweiten Version die Indizes von c bei 1 beginnen lassen wollen, so ist diese Übereinstimmung offensichtlich nicht mehr gegeben. Wie müssen wir die Indexgrenzen für c wählen, um für alle Werte im Bereich von minv bis maxv einen Zähler zur Verfügung zu haben?
Wir betrachten hierzu einfach zwei Beispiele:
· Ist minv = 3 und maxv = 6, so
benötigen wir Zähler für die Werte
3, 4, 5, 6
und die Indizes von c müssten sein:
1, 2, 3, 4
Die Häufigkeit des Werts 3 speichern wir in c(1), den des Werts 4 in c(2) usw.
· Ist minv = -2 und maxv = 6, so
brauchen wir Zähler für die Werte
-2, -1, 0, 1, 2, 3, 4, 5, 6
und benötigen folgende Indizes für c:
1, 2, 3, 4 ,5, 6, 7, 8, 9
Die Häufigkeit des Werts -2 speichern wir in c(1), den des Werts -1 in c(2) usw.
Anhand der Beispiele können Sie sich leicht davon überzeugen, dass allgemein gilt:
· Für den Wertebereich minv bis max
müssen die Indizes des Zählerarrays c von 1 bis (maxv – minv +1) laufen.
· Für den Wert a(i) ist c(a(i) – minv + 1) der zuständige Zähler. In umgekehrter Betrachtungsweise gilt: der Zähler c(i) bezieht sich auf den Wert i + minv -1.
Und hier ist der Code der zweiten, flexibleren Fassung:
Public Function CountingSort(ByRef a() As Integer, _
ByVal maxv As Integer, _
ByVal minv As Integer) As Integer()
Dim c() As Integer 'counts
Dim s() As Integer 'sorted array (result)
ReDim c(1 To maxv - minv + 1)
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, z As Integer
'counting occurrences of values
For i = 1 To UBound(a)
c(a(i) - minv + 1) = c(a(i) - minv + 1) + 1
Next i
'deriving sorted array from counts
z = 0
For i = minv To maxv
For j = 1 To c(i - minv + 1)
z = z + 1
s(z) = i
Next j
Next i
CountingSort = s
End Function
Die Doppelschleife im zweiten Teil ist etwas schwieriger zu lesen als die der simplen Version, tut aber im Grunde dasselbe: die äußere Schleife (i-Schleife) geht alle Werte des Wertebereichs von a bzw. alle Elemente des Zählerarrays durch, die innere Schleife schreibt den Wert so oft in das Array s, wie es dem Zähler entspricht. Das Element c(i – minv +1) des Zählerarrays ist das Element, das die Häufigkeit des Werts i enthält (s. oben).
Alternativ könnten wir diese Doppelschleife auch folgendermaßen formulieren:
z = 0
For i = 1 To UBound(c)
For j = 1 To c(i)
z = z + 1
s(z) = i + minv - 1
Next j
Next i
Die Betrachtungsweise ist hier gegenüber der ersten Formulierung umgedreht, aber der Effekt ist derselbe. Wir müssen berücksichtigen, dass dem Element an der Stelle i des Zählerarrays c nicht der Wert i der Wertebereichs entspricht, sondern der Wert i + minv -1.
Die Animation
Die Animation veranschaulicht den Ablauf der zweiten, flexibleren Version. Sie arbeitet mit Zufallszahlen. Es wird ein Array mit 15 Zahlen im Wertebereich (-2, 7) erzeugt. Dieses Array wird als Input für die Sortierfunktion benutzt. Da die Zahlen zufällig erzeugt werden, kann es durchaus vorkommen, dass im Input-Array nicht alle Werte des Wertebereichs vertreten sind. Der Sortierfunktion werden jedoch stets die Werte minv = -2 und maxv = 7 übermittelt, gleichgültig, ob diese Werte tatsächlich im erzeugten Array vorhanden sind.
Der Betrachter startet das Programm durch Anklicken einer Schaltfläche auf dem Arbeitsblatt CountingSort. Oberhalb der Schaltfläche vollzieht sich die Animation. Am ihrem Ende sieht man auf dem Arbeitsblatt drei voneinander abgesetzte Zonen. Es sind, von oben nach unten (s. Bild unten):
- Die zu sortierende Zahlenliste
- Das Zählerarra
- Die Liste der sortierten Zahlen
Die Animation beginnt für den Betrachter mit der Anzeige der generierten Zahlen, welche zu sortieren sind.
Dann folgt der erste Hauptschritt des Algorithmus, die Auszählung der Werte. Hierzu wird zunächst das mit Nullen gefüllte Zählerarray unterhalb der zu sortierenden Zahlen aufgebaut (Zeile 10). Unmittelbar darüber, in Zeile 9, werden die zugehörigen Werte des Wertebereichs angezeigt. Dieser Aufbau geschieht Schritt für Schritt, so dass der Betrachter gedanklich folgen kann. Danach beginnt die eigentliche Auszählung. Dabei werden die einzelnen Zellen der unsortierten Liste nacheinander besucht und markiert. Vom besuchten Element wandert dann ein Pfeil zur zugehörigen Spalte des Zählerarrays, wo dann die Häufigkeit jeweils um 1 erhöht wird.
Im zweiten Hauptschritt wird sodann die Liste der sortierten Zahlen aufgebaut. Hierzu werden nacheinander, für den Betrachter gut zu verfolgen, alle Spalten des Zählerarrays besucht. Der Besuch der Spalte wird für den Betrachter durch eine Graufärbung der betreffenden Zellen sichtbar gemacht. Unmittelbar nach jedem Zellenbesuch werden die Werte, auf die sich die betreffende Zelle bezieht, unten in die sortierte Liste geschrieben.
Das Animationsprogramm
Das Programm hat eine dreischichtige Architektur, welche der in Animationen | Ereignisgesteuerte Animation beschriebenen entspricht. Die Schichten sind im Einzelnen:
-
Das UI: Hier besteht es nur
aus einer sehr kleinen Prozedur, welche gestartet wird, wenn der Benutzer auf die Schaltfläche mit der Aufschrift „Start Animation“ klickt, die sich auf dem Arbeitsblatt CountingSort
befindet.
-
Die Klasse CountSortAnimator, welche ein Objekt der
unteren Schicht mit der Durchführung des Sortieralgorithmus beauftragt, und dann die Ereignisse auffängt, die beim Sortieren ausgelöst werden, und diese Ereignisse in Animationsausgaben
umwandelt.
- Die Klasse CountSort mit der darin befindlichen Funktion CountingSort, welche mit den für die Animation benötigten Ereignissen ausgestattet wurde.
Wir betrachten nun die einzelnen Schichten, beginnend bei der untersten Schicht:
Die Klasse CountSort mit der Funktion CountingSort
Im folgenden Code sind alle Anweisungen enthalten, die in der Normalfassung der Funktion ebenfalls enthalten sind. Die Ergänzungen, welche für die ereignisgesteuerte Animation notwendig sind, wurden grün hervorgehoben.
Zwei Ereignisse wurden hinzugefügt:
· Das Ereignis counted wird ausgelöst, wenn der Algorithmus in der ersten Phase des Algorithmus ein Element des Arrays a besucht und den entsprechenden Zähler im Zählerarray c fortschreibt. Der Parameter aI bezeichnet den Index des besuchten Elements im Parameter-Array a, cI ist der Index des dazu gehörigen Zählers im Zählerarray c, und ct ist die im Zähler gespeicherte Anzahl nach der Fortschreibung.
· Das Ereignis derived tritt auf, wenn ein Element in das Array s der sortierten Zahlen geschrieben wurde. Der Parameter cI ist der Index des Elements im Zählerarray c, welches für das Ausschreiben ursächlich ist, sI ist der Index des Elements im Array s, in das der Wert geschrieben wird, und v ist der ausgeschriebene Wert selbst.
Public Event counted(ByVal aI As Integer, ByVal cI As Integer, ByVal ct As Integer)
Public Event derived(ByVal cI As Integer, ByVal sI As Integer, ByVal v As Integer)
Public Function CountingSort(ByRef a() As Integer, _
ByVal maxv As Integer, _
ByVal minv As Integer) As Integer()
Dim c() As Integer 'counts
Dim s() As Integer 'sorted array (result)
ReDim c(1 To maxv - minv + 1)
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, z As Integer
'counting occurrences of values
For i = 1 To UBound(a)
c(a(i) - minv + 1) = c(a(i) - minv + 1) + 1
RaiseEvent counted(i, a(i) - minv + 1, c(a(i) - minv + 1))
Next i
'deriving sorted array from counts
z = 0
For i = minv To maxv
For j = 1 To c(i - minv + 1)
z = z + 1
s(z) = i
RaiseEvent derived(i - minv + 1, z, s(z))
Next j
Next i
CountingSort = s
End Function
Die Klasse CountSortAnimator
Die Prozedur doAnimation stellt den Kern dieser Klasse dar. Sie trifft die Vorbereitungen für die Animation und stößt die Durchführung des Sortierungsalgorithmus an. Die Prozedur rndNumbers leistet der Prozedur doAnimation Zuträgerdienste, indem sie das gewünschte Array von Zufallszahlen erzeugt.
Die beiden Ereignisprozeduren am Ende des Codes fangen die Ereignisse während der Sortierung auf und wandeln sie in die Animationsausgaben um. Sie streuen dabei zeitliche Verzögerungen ein, damit der Benutzer die Animation verfolgen kann.
Die Prozeduren delay und yxyArrow sind Hilfsprozeduren, welche von den Ereignisprozeduren aufgerufen werden. Beachten Sie, dass die in yxyArrow veranlassten Verzögerungen nur Bruchteile der Grundverzögerung sind. Während an anderen Stellen der Animation eine stärkere Verzögerung sinnvoll ist, damit der Betrachter gedanklich folgen kann, ist beim Transport des Wertes eine flüssige Bewegung angebracht.
Private WithEvents cs As CountSort 'object doing the sort
Private dur As Single 'delay between moves
Private oldRn As Range 'where old array is displayed
Private cntRn As Range 'where counts are shown
Private newRn As Range 'where sorted array is displayed
Private w As Worksheet
Public Sub doAnimation(ByVal outw As Worksheet, _
ByVal duration As Single)
Dim i As Integer
Set cs = New CountSort
Dim a() As Integer
a = rndNumbers(15)
Set w = outw
Set oldRn = Range(w.Cells(5, 2), w.Cells(5, 16))
Set cntRn = Range(w.Cells(9, 2), w.Cells(10, 11))
Set newRn = Range(w.Cells(14, 2), w.Cells(14, 16))
dur = duration
w.Cells.Clear
w.Activate
w.Cells(1, 1).Select
w.Cells.HorizontalAlignment = xlCenter
w.Cells.VerticalAlignment = xlCenter
oldRn = a
w.Cells(9, 13) = "value"
w.Cells(10, 13) = "count"
For i = 1 To 10
delay dur
w.Cells(9, 1 + i) = -2 + i - 1
w.Cells(10, 1 + i) = 0
Next i
cs.CountingSort a, 7, -2
End Sub
'generates n numbers of type Double (values are integers)
'-----------------------------------------------------------------------------
Public Function rndNumbers(ByVal n As Integer) As Integer()
Dim i As Integer
Dim r() As Integer
ReDim r(1 To n)
For i = 1 To n
r(i) = Int(-2 + (7 - (-2)) * Rnd)
Next i
rndNumbers = r
End Function
'causes a delay
'---------------------
Private Sub delay(ByVal duration As Single)
Dim t As Single
t = Timer
Do While Timer < t + duration
DoEvents
Loop
End Sub
'arrow moves from (oldR,oldC) to (newR, newC)
'-------------------------------------------------------------------
Private Sub yxyArrow(ByVal oldR As Integer, ByVal oldC As Integer, _
ByVal newR As Integer, ByVal newC As Integer)
Dim t As String, t1 As String, t2 As String, t3 As String
t1 = ChrW(8595) 'arrow downwards
t2 = ChrW(8592) 'arrow left
t3 = ChrW(8594) 'arrow right
Dim i As Integer
t = w.Cells(oldR, oldC)
'y-direction
t = t1
w.Cells(oldR, oldC) = t
delay dur / 5
w.Cells(oldR + 1, oldC) = t
w.Cells(oldR, oldC) = ""
'x-direction
If newC < oldC Then
t = t2
For i = oldC To newC Step -1
w.Cells(oldR + 1, i) = t
delay dur / 5
w.Cells(oldR + 1, i) = ""
Next i
Else
t = t3
For i = oldC To newC
w.Cells(oldR + 1, i) = t
delay dur / 5
w.Cells(oldR + 1, i) = ""
Next i
End If
'y-direction
t = t1
w.Cells(oldR + 1, newC) = t
delay dur / 5
w.Cells(oldR + 1, newC) = ""
w.Cells(newR, newC) = t
delay dur / 5
w.Cells(newR, newC) = ""
End Sub
Private Sub cs_counted(ByVal aI As Integer, ByVal cI As Integer, ByVal ct As Integer)
oldRn(aI).Interior.ThemeColor = xlThemeColorDark2
delay dur
yxyArrow 6, aI + 1, 8, cI + 1
cntRn(2, cI) = ct
delay dur
End Sub
Private Sub cs_derived(ByVal cI As Integer, ByVal sI As Integer, ByVal v As Integer)
cntRn(1, cI).Interior.ThemeColor = xlThemeColorDark2
cntRn(2, cI).Interior.ThemeColor = xlThemeColorDark2
delay dur
newRn(1, sI) = v
newRn(1, sI).Interior.ThemeColor = xlThemeColorDark2
delay dur
End Sub
Die Prozedur zum Starten der Animation
Diese Prozedur wird durchgeführt, wenn der Benutzer auf die Schaltfläche zum Starten der Animation klickt.
Public Sub startCountSortAnimator()
Dim csa As CountSortAnimator
Set csa = New CountSortAnimator
csa.doAnimation Worksheets("CountingSort"), 1
End Sub
Download
