Sortieren einer Matrix bzw. eines Arbeitsblattbereichs

 

In der folgenden kleinen Fallstudie wird zunächst eine Funktion sortMatrix vorgestellt, welche eine Matrix vom Typ Double aufsteigend sortiert.  Die Fallstudie ist in zweierlei Hinsicht interessant

  • Es wird das Prinzip der Zerlegung bzw. der Delegation verwendet. Damit werden Verständlichkeit, Wartbarkeit und Wiederverwendbarkeit der Anwendung gefördert.
  • Von den beiden Unterfunktionen, an die von der Hauptfunktion Aufgaben delegiert werden, werden jeweils unterschiedliche Lösungen gezeigt. Anhand dieser Lösungen wird gezeigt, wie unterschiedlich mit den Indizes von Arrays gearbeitet werden kann.
  • Die Funktion ist nicht als benutzerdefinierte Funktion verwendbar, weil ihr Argument ein Array ist. Mit geringem Aufwand und mit Verwendung der Einwickeltechnik kann man diese Funktion jedoch in eine benutzerdefinierte verwandeln, also eine Funktion, welche einen Bereich eines Arbeitsblatts sortiert.

 

Sortierungsbeispiel:

 

     Aus der Matrix

 

               4     6     2

               5     1     3

 

     wird die Matrix

 

               1     2     3

               4     5     6

 

 

Lösung

 

Bei der Lösung wollen wir beachten, dass die Funktion sortMatrix keine Nebeneffekte verursachen soll. Insbesondere soll das von der aufrufenden Stelle übergebene Array dort durch die Durchführung der Funktion nicht verändert werden. Außerdem wollen wir alle Array-Indizes mit 1 beginnen lassen.

 

Wir verfolgen die folgende Strategie bei der Sortierung:

 

  • Die Matrix wird in eine Liste in Form eines eindimensionalen Arrays überführt
  • Dieses eindimensionale Array wird sortiert
  • Das eindimensionale Array wird in eine Matrix zurückverwandelt. Die ursprüngliche Dimension der Matrix bleibt dabei erhalten.

 

Zur Umsetzung dieser Strategie programmieren wir zunächst drei Unterfunktionen. An diese Unterfunktionen soll sortMatrix dann Teilaufgaben delegieren:

 

    Public Function MatrixToList (ByRef a() As Double) As Double()
    Public Function InsertionSort (ByRef a() As Double) As Double()
    Public Function ListToMatrix (ByRef a() As Double, ByVal m As Integer) As Double()

 

Der Parameter m der letzten Funktion bezeichnet die Anzahl der Zeilen der Ergebnismatrix.

 

Wir beginnen mit der Funktion MatrixToList, welche eine Matrix in ein eindimensionales Array verwandelt:

 

Public Function MatrixToList(ByRef a() As Double) As Double()

    Dim t() As Double

    Dim m As Integer, n As Integer, i As Integer, j As Integer

    m = UBound(a, 1)        'Anzahl der Zeilen

    n = UBound(a, 2)        'Anzahl der Spalten

    ReDim t(1 To m * n)

    For i = 1 To m          'übertrage alle Elemente

        For j = 1 To n

            t((i - 1) * n + j) = a(i, j)

        Next j

    Next i

    MatrixToList = t

End Function

 

Beachten Sie den Rumpf der inneren Schleife. Darin werden die Indizes im Zielarray in Abhängigkeit von den Indizes i und j des Elements in der Matrix ausgedrückt, das in dem aktuellen Schleifendurchlauf gerade übertragen wird. Diese Lösung mag manchem Leser der Funktion schwer verständlich sein. Wir können die Lesbarkeit der Funktion verbessern, müssen aber hierfür eine zusätzliche Variable p einführen, einen Positionszähler für das Zielarray. Die Funktion lautet in dieser zweiten Fassung folgendermaßen:

 

Public Function MatrixToList (ByRef a() As Double) As Double()

    Dim t() As Double

    Dim m As Integer, n As Integer, i As Integer, j As Integer, p As Integer

    m = UBound(a, 1)        'Anzahl der Zeilen

    n = UBound(a, 2)        'Anzahl der Spalten

    ReDim t(1 To m * n)

    p = 0

    For i = 1 To m          'übertrage alle Elemente

        For j = 1 To n

            p = p + 1

            t(p) = a(i, j)

        Next j

    Next i

    MatrixToList = t

End Function

 

Nun realisieren wir die Funktion ListToMatrix, welche das eindimensionale Array nach der Sortierung wieder in eine Matrix der ursprünglichen Dimension zurück verwandeln soll. Da diese ursprüngliche Dimension sich nicht eindeutig aus dem Umfang des eindimensionalen Arrays ergibt, fügen wir die Zeilenzahl m der Zielmatrix als zweiten Parameter hinzu. Wir nehmen stillschweigend an, dass die Anzahl der Elemente im Array a ohne Rest durch m teilbar ist.

 

Public Function ListToMatrix(ByRef a() As Double, ByVal m As Integer) As Double()

    Dim n As Integer, i As Integer

    n = UBound(a) \ m                'Anzahl der Spalten in der Zielmatrix

    Dim r() As Double                'Zielmatrix

    ReDim r(1 To m, 1 To n)

    For i = 1 To UBound(a)           'übertrage alle Elemente

        r((i - 1) \ n + 1, i - ((i - 1) \ n) * n) = a(i)

    Next i

    ListToMatrix = r

End Function

 

Im Rumpf der Schleife werden die Indizes des jeweils zu besetzenden Matrixelements in Abhängigkeit vom Index des eindimensionalen Arrays ausgedrückt. Auch für diese Funktion erhalten wir eine besser lesbare Funktion, wenn wir einen Positionszähler für das eindimensionale Array einführen:

 

Public Function ListToMatrix (ByRef a() As Double, ByVal m As Integer) As Double()

    Dim n As Integer, i As Integer, j As Integer, p As Integer

    n = UBound(a) \ m                'Anzahl der Spalten in der Zielmatrix

    Dim r() As Double                'Zielmatrix

    ReDim r(1 To m, 1 To n)

    p = 0

    For i = 1 To m          'übertrage alle Elemente

        For j = 1 To n

            p = p + 1

            r(i, j) = a(p)

        Next j

    Next i

    ListToMatrix = r

End Function

 

Von den beiden Fassungen der Funktion kann, genauso wenig wie bei MatrixToList, keine als die eindeutig bessere bezeichnet werden. Lesbarkeit und sparsame Verwendung von Variablen stehen hier miteinander in Konflikt. Die Wahl ist eine der persönlichen Präferenz.

 

Nun programmieren wir die Funtion InsertionSort für die Sortierung eines eindimensionalen Arrays. Wir wählen hierfür eine Variante des bekannten Sortierens durch Einfügen:

 

Public Function InsertionSort(ByRef a() As Double) As Double()

    Dim s() As Double                  ‘Zielarray

    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

 

Bitte beachten Sie, dass die Sortierung hier nicht „in place“ geschieht, wie in anderen Fassungen von insertion sort üblich. Damit vermeiden wir den Nebeneffekt, dass die Quellmatrix an der aufrufenden Stelle ebenfalls sortiert wird.

 

Die Programmierung der Gesamtfunktion sortMatrix gerät infolge der Auslagerung aller Teilaufgaben sehr kurz. Der Rumpf besteht nur aus einer einzigen Zeile:

 

Public Function sortMatrix(ByRef m() As Double) As Double()

    sortMatrix = ListToMatrix(InsertionSort(MatrixToList(m)), UBound(m, 1))

End Function

 

 

 

 

Eine benutzerdefinierte Funktion, die Bereiche sortiert

 

Mit Hilfe der Einwickeltechnik können wir aus sortMatrix mit sehr geringem Aufwand eine UDF ableiten, welche zur Sortierung von Bereichen eines Arbeitsblatts eingesetzt werden kann. Dabei kommt die bereits bekannte Umwandlungsfunktion RangeToDblArray (s. Matrixoperationen) zum Einsatz:

 

'UDF-Version von sortMatrix

Public Function sortMatrixUDF(ByVal r As Range) As Double()

    sortMatrixUDF = sortMatrix(RangeToDblArray(r))

End Function