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 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 Ü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, wur­den 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 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

    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

AnimationSelectionSort.zip
Komprimiertes Archiv im ZIP Format 26.7 KB