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 (maxvminv +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, wur­den 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 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 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

CountSortAnim.zip
Komprimiertes Archiv im ZIP Format 34.2 KB