Ereignisgesteuerte Animation: Sortieren durch Auswahl
Event-driven Animation of Selection Sort - Abstract
In this case study we show how Selection Sort, a well-known and frequently used method for sorting, can be animated using the technique of event-driven animation which has already been described on another subpage (Ereignisgesteuerte Animation / event-driven animation).
Download
The workbook containing the entire code can be downloaded at the bottom of this subpage.
Sortieren durch Auswahl – der Algorithmus
Sortieren durch Auswahl (selection sort) ist eine der bekanntesten und eingängigsten Sortiermethoden. Das Prinzip ist einfach. Angenommen, wir möchten eine Liste von Zahlen sortieren. Der Einfachheit halber wollen wir uns vorstellen, dass jeder Wert dieser Liste auf ein Kärtchen geschrieben ist und die Kärtchen nebeneinander vor uns auf dem Tisch liegen. Wir gehen nun die Reihe der Kärtchen durch, suchen das mit dem kleinsten Wert und nehmen es heraus. Gibt es mehrere Kärtchen, welche diesen Wert aufweisen, nehmen wir irgendeines davon, am besten gleich das erste. Das entnommene Kärtchen legen wir nun unterhalb der Kartenreihe auf den Tisch, ganz nach links, als Beginn einer neuen, sortierten Kartenreihe. In der reduzierten oberen Kartenreihe suchen wir sodann wieder das kleinste Element, nehmen es heraus und legen es rechts an die untere Kartenreihe an. Und so geht es weiter. Wir suchen immer das kleinste Kärtchen der oberen Reihe, entnehmen es und legen es rechts an die untere Reihe an. Dies tun wir, bis aus der oberen Reihe alle Kärtchen entfernt sind.
In der folgenden Funktion entspricht das Parameter-Array a der oberen Kärtchenreihe, das Array s der darunterliegenden, neu aufzubauenden Reihe. Weil das Entnehmen eines Werts aus dem Array eine aufwändige Angelegenheit ist, entfernen wir die aus a zu entnehmenden Werte nicht wirklich, sondern bedienen uns eines Tricks. Wir führen nebenbei ein weiteres Array h vom Typ Boolean, das genau so viele Elemente enthält wie a. Ein True bei h(i) bedeutet, dass sich der Wert an der Stelle i noch in der oberen Reihe befindet, ein False bei h(i) bedeutet, dass der Wert schon entfernt und an die untere Reihe angefügt worden ist.
In der großen For-Schleife wird ein Element von a nach dem anderen in das Array s gebracht. Dies geschieht jeweils in zwei Schritten. Zuerst wird das kleinste aus den noch in a verbliebenen Elementen gefunden, dann wird dieses Element aus a „entnommen“ und in s eingebracht.
Public Function SelectionSort(ByRef a() As Double) As Double()
Dim s() As Double
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, numr As Integer, minpos As Integer
Dim h() As Boolean
numr = UBound(a)
ReDim s(1 To numr)
ReDim h(1 To numr)
For i = 1 To numr
h(i) = True
Next i
For i = 1 To numr
'search position of smallest row in a
Dim found As Boolean
found = False
minpos = 0
Do While Not found
minpos = minpos + 1
If h(minpos) Then found = True
Loop
For j = minpos To numr
If h(j) Then
If a(j) < a(minpos) Then minpos = j
End If
Next j
'transfer smallest row from a to s
s(i) = a(minpos)
h(minpos) = False
Next i
SelectionSort = s
End Function
Die Animation
Die Animation arbeitet mit Zufallszahlen. Wenn der Benutzer den Startknopf drückt, so wird ein Array mit 15 Zahlen erzeugt. Dieses Array wird als Input für die Sortierfunktion benutzt. Die Zufallszahlen werden in der oberen Zeile des Animationsbereichs angezeigt (s. Bild unten).
Das folgende Bild zeigt eine Momentaufnahme mitten in der Animation. Die untere Zeile entspricht dem Array s der sortierten Werte aus der Sortierfunktion. Die bereits eingefügten Elemente sind in der oberen Zeile, welche dem Array a der Funktion entspricht, grau unterlegt.
Wir sehen im Bild einen Zwischenstand während des Übertragens des Elements mit dem Wert 53. Der eingezeichnete Pfeil ist in der Animation nicht sichtbar. Stattdessen wird der einzufügende Wert entlang der Pfeillinie von Zelle zu Zelle transportiert, bis er die Zielzelle erreicht hat.
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 eine Schaltfläche klickt, die sich auf dem Arbeitsblatt SelectionSort befindet.
- Die Klasse SelectionSortAnimator, 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 DbsSort, von der hier nur die Funktion SelectionSort und die mit ihr verbundenen Ereignisse benötigt werden.
Wir betrachten nun die einzelnen Schichten, beginnend bei der untersten Schicht:
Die Klasse DblSort mit der Funktion SelectionSort
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 SSexam wird ausgelöst, wenn der Algorithmus bei der Suche nach dem kleinsten Wert ein Element untersucht („examiniert“). Der Parameter pos bezeichnet die Position dieses Elements im Parameter-Array a
- Das Ereignis SStransfer tritt auf, wenn ein Element vom alten Array a in das neue Array s verlegt wird. Der Parameter fromIndex gibt die Position des Elements in a an, der Parameter toIndex die Position in s.
Public Event SSexam(ByVal pos As Integer)
Public Event SStransfer(ByVal fromIndex As Integer, ByVal toIndex As Integer)
Public Function SelectionSort(ByRef a() As Double) As Double()
Dim s() As Double
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, numr As Integer, minpos As Integer
Dim h() As Boolean
numr = UBound(a)
ReDim s(1 To numr)
ReDim h(1 To numr)
For i = 1 To numr
h(i) = True
Next i
For i = 1 To numr
'search position of smallest row in a
Dim found As Boolean
found = False
minpos = 0
Do While Not found
minpos = minpos + 1
If h(minpos) Then found = True
Loop
For j = minpos To numr
If h(j) Then
RaiseEvent SSexam(j)
If a(j) < a(minpos) Then minpos = j
End If
Next j
'transfer smallest row from a to s
s(i) = a(minpos)
h(minpos) = False
RaiseEvent SStransfer(minpos, i)
Next i
SelectionSort = s
End Function
Die Klasse SelectionSortAnimator
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 yxy sind Hilfsprozeduren, welche von den Ereignisprozeduren aufgerufen werden.
Beachten Sie, dass die in yxy 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 dbls As DblSort 'object doing the sort
Private dur As Single 'delay between moves
Private oldR As Range 'where old array is displayed
Private newR As Range 'where sorted array is shown
Private w As Worksheet
Public Sub doAnimation(ByVal outw As Worksheet, _
ByVal duration As Single)
Set dbls = New DblSort
Dim a() As Double
a = rndNumbers(15)
Set w = outw
Set oldR = Range(w.Cells(5, 2), w.Cells(5, 16))
Set newR = Range(w.Cells(9, 2), w.Cells(9, 16))
dur = duration
w.Cells.Clear
w.Activate
oldR = a
dbls.SelectionSort a
End Sub
'generates n numbers of type Double (values are integers)
'-----------------------------------------------------------------------------------
Public Function rndNumbers(ByVal n As Integer) As Double()
Dim i As Integer
Dim r() As Double
ReDim r(1 To n)
For i = 1 To n
r(i) = Int(1 + (100 - 1) * 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
'transports a value from oldR to newR
'-----------------------------------------------------
Private Sub yxy(ByVal oldR As Integer, ByVal oldC As Integer, _
ByVal newR As Integer, ByVal newC As Integer)
Dim t As Integer, i As Integer
t = w.Cells(oldR, oldC)
'y-direction
w.Cells(oldR + 1, oldC) = t
delay dur / 10
w.Cells(oldR + 1, oldC) = ""
'x-direction
If newC < oldC Then
For i = oldC To newC Step -1
w.Cells(oldR + 2, i) = t
delay dur / 15
w.Cells(oldR + 2, i) = ""
Next i
Else
For i = oldC To newC
w.Cells(oldR + 2, i) = t
delay dur / 15
w.Cells(oldR + 2, i) = ""
Next i
End If
'y-direction
w.Cells(oldR + 3, newC) = t
delay dur / 10
w.Cells(oldR + 3, newC) = ""
w.Cells(newR, newC) = t
End Sub
'event: element is examined when searching for minpos
'------------------------------------------------------------------------------
Private Sub dbls_SSexam(ByVal pos As Integer)
oldR.Cells(1, pos).Select
delay dur / 6
End Sub
'event: element is transferred from old to new array
'------------------------------------------------------------------------
Private Sub dbls_SStransfer(ByVal fromIndex As Integer, ByVal toIndex As Integer)
oldR.Cells(1, fromIndex).Select
delay dur
oldR.Cells(1, fromIndex).Interior.ThemeColor = xlThemeColorDark2
delay dur
yxy 5, fromIndex + 1, 9, toIndex + 1 'transport from oldR to newR
newR.Cells(1, toIndex).Interior.ThemeColor = xlThemeColorAccent1
newR.Cells(1, toIndex).Interior.TintAndShade = 0.799981688894314
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 startSelectionSortAnimator()
Dim ssa As SelectionSortAnimator
Set ssa = New SelectionSortAnimator
ssa.doAnimation Worksheets("SelectionSort"), 1
End Sub
Download
