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 Auf­nehmen 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 auf­zu­nehmenden 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 ein­gefügt wer­den 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 an­de­ren 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 einzu­stecken­de, wird nach rechts ge­schoben, so dass links von ihr eine Lücke entsteht.

 

Der Platz ist gefun­den, so­bald man bei einer Karte anlangt, die nicht größer als die einzusteckende ist oder wenn man ganz am linken Ende ange­langt ist. Letzteres geschieht offensichtlich nur dann, wenn die neu einzu­steckende 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 einge­fü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, wur­den 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 Anima­tion 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

workbook: Animation of Insertion Sort
IS_Animation.zip
Komprimiertes Archiv im ZIP Format 27.1 KB