Ereignisgesteuerte Animation: Sortieren durch Einfügen
Event-driven Animation of Insertion Sort - Abstract
In this case study we show how Insertion Sort, a well-known and frequently used method of sorting, can be animated using the technique of event-driven animation which has already been described on another subpage (see Ereignisgesteuerte Animation / event-driven animation).
Download
The workbook containing the entire code can be downloaded at the bottom of this subpage.
Sortieren durch Einfügen – der Algorithmus
Sortieren durch Einfügen (insertion sort) ist eine der bekanntesten Sortiermethoden. Das Prinzip ist einfach und eingängig. Es entspricht der Art und Weise, wie Kartenspieler ihre Karten beim Aufnehmen ordnen. Vor dem Spieler liegt der Stapel mit den aufzunehmenden Karten. Jedesmal, wenn er eine Karte aufnimmt, macht er Platz für diese Karte, indem er alle größeren Karten nach rechts schiebt und so eine Lücke an der richtigen Stelle schafft. Dann steckt er die Karte in diese Lücke.
Wenn auch das Prinzip sehr einfach ist, erfordert die Programmierung doch etwas Feinarbeit, wie der folgende Code zeigt. Der Grobablauf ist gut erkennbar. Das Parameter-Array a entspricht dem aufzunehmenden Kartenstapel, das Array s den in der Hand des Spielers befindlichen sortierten Karten.
Die erste Karte wird einfach übernommen. Für alle weiteren Karten muss der richtige Platz gesucht und frei gemacht werden. Die einzufügende Karte ist jeweils die Karte j. Wenn Karte j eingefügt werden soll, stecken bereits j-1 Karten. Der Spieler sucht den Einsteckplatz, indem er auf der rechten Seite der bereits steckenden Karten beginnt, also bei Karte j-1, und eine Karte nach der anderen mit der neu einzusteckenden Karte vergleicht. Wir benutzen den Index i, um die Karte zu bezeichnen, mit der gerade verglichen wird. Jede Karte i, die größer ist als die einzusteckende, wird nach rechts geschoben, so dass links von ihr eine Lücke entsteht.
Der Platz ist gefunden, sobald man bei einer Karte anlangt, die nicht größer als die einzusteckende ist oder wenn man ganz am linken Ende angelangt ist. Letzteres geschieht offensichtlich nur dann, wenn die neu einzusteckende Karte die kleinste von allen ist. Die Variable found ist nötig, damit die Platzsuche abgebrochen wird, sobald der richtige Platz gefunden wird.
Public Function InsertionSort(ByRef a() As Double) As Double()
Dim s() As Double
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, found As Boolean
s(1) = a(1)
For j = 2 To UBound(a)
i = j - 1
found = False
Do While i > 0 And Not found
If s(i) > a(j) Then
s(i + 1) = s(i)
i = i - 1
Else
found = True
End If
Loop
s(i + 1) = a(j)
Next j
InsertionSort = 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 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 Einfügens des Elements mit dem Wert 2. Im Array s sind bereits alle größeren Werte nach rechts verschoben worden, so dass die Lücke zum Einfügen schon geschaffen ist. In diesem Fall ist es das linke Ende.
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 Lücke 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 InsertionSort befindet.
- Die Klasse InsertionSortAnimator, 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 DblSort, von der hier nur die Funktion InsertionSort 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 InsertionSort
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. Drei Ereignisse wurden hinzugefügt:
- Das Ereignis nextElement wird ausgelöst, wenn der Algorithmus beginnt, ein Element einzufügen. Der Parameter index bezeichnet die Position dieses Elements im Parameter-Array a
- Das Ereignis shift tritt auf, wenn eines der bereits in Array s eingefügten Elemente um eine Position nach rechts verschoben wird. Bei dem Parameter toIndex handelt es sich um die Position in Array s, zu der die Verschiebung erfolgt. Die Startposition der Verschiebung muss nicht angegeben werden, denn sie ist immer um 1 niedriger als die Zielposition.
- Das Ereignis placeFound findet statt, wenn die Suche nach dem richtigen Platz für ein einzufügendes Element abgeschlossen ist. Der Parameter fromIndex bezeichnet die Position des Elements in Array a, toIndex ist die Position des Elements im Array s.
Public Event nextElement(ByVal index As Integer)
Public Event shift(ByVal toIndex As Integer)
Public Event placeFound(ByVal fromIndex As Integer, ByVal toIndex As Integer)
Public Function InsertionSort(ByRef a() As Double) As Double()
Dim s() As Double
ReDim s(1 To UBound(a))
Dim i As Integer, j As Integer, found As Boolean
s(1) = a(1)
RaiseEvent nextElement(1)
RaiseEvent placeFound(1, 1)
For j = 2 To UBound(a)
RaiseEvent nextElement(j)
i = j - 1
found = False
Do While i > 0 And Not found
If s(i) > a(j) Then
s(i + 1) = s(i)
RaiseEvent shift(i + 1)
i = i - 1
Else
found = True
End If
Loop
RaiseEvent placeFound(j, i + 1)
s(i + 1) = a(j)
Next j
InsertionSort = s
End Function
Die Klasse InsertionSortAnimator
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 drei Ereignisprozeduren am Ende des Codes fangen die Ereignisse während der Sortierung auf und wandeln sie in die Animationsausgaben um. Sie fügen 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
dur = duration
w.Cells.Clear
w.Activate
Set oldR = Range(w.Cells(5, 2), w.Cells(5, 16))
Set newR = Range(w.Cells(9, 2), w.Cells(9, 16))
oldR = a
dbls.InsertionSort 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 procedures
'-------------------------
Private Sub dbls_nextElement(ByVal index As Integer)
oldR.Cells(1, index).Select
delay dur
End Sub
Private Sub dbls_placeFound(ByVal fromIndex As Integer, ByVal toIndex As Integer)
oldR.Cells(1, fromIndex).Interior.ThemeColor = xlThemeColorDark2
yxy 5, fromIndex + 1, 9, toIndex + 1 'transport from oldR to newR
delay dur
End Sub
Private Sub dbls_shift(ByVal toIndex As Integer)
newR.Cells(1, toIndex) = newR.Cells(1, toIndex - 1)
newR.Cells(1, toIndex - 1) = ""
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 startInsertionSortAnimator()
Dim isa As InsertionSortAnimator
Set isa = New InsertionSortAnimator
isa.doAnimation Worksheets("InsertionSort"), 1
End Sub
Download
