Datenfelder zusammenfügen und sortieren

Wie kann man schnell zwei Datenfelder sortiert zusammenfügen? Angenommen wir haben zwei zweidimensionale Datenfelder. Nennen wir sie Daten1(100,2) und Daten2(100,2), zum Beispiel x- und y-Werte. Sollte man die Datenfelder, mit einer Reihe von if-Abfragen, sortiert in ein drittes Datenfeld schreiben? Oder ist es besser beide Datenfelder (stupide) aneinander zuhängen und anschließend mit Quicksort zu sortieren?

In der Funktion Sort2ArraysIn1_1 habe ich die beiden Datenfelder dbl1 und dbl2 sortiert ineinander gefügt. Die Funktion Sort2ArraysIn1_2 hängt dbl2 an dbl1 an und sortiert anschließend mit dem noch auf meiner alten Seite vorgestellten Quicksort-Algorithmus (angepasst für 2-dimensionale Arrays).

Das Ergebnis

Man hat es ja schon geahnt, aber tatsächlich ist es um den Faktor 2 schneller die bereits sortierten Datenfelder sortiert ineinander zu fügen. Einfaches Anfügen und anschließendes Sortieren ist deutlich langsamer.

Der Sieger-Quellcode und weitere Beispiele im Anhang:

Public Function Sort2ArraysIn1_1(dbl1() As Double, dbl2() As DoubleAs Double()
    Dim i1 As Long, i2 As Long
    Dim dbl3() As Double
    i1 = 1
    i2 = 1

    ReDim dbl3(UBound(dbl1) + UBound(dbl2), 2)
    Do While i1 <= UBound(dbl1) Or i2 <= UBound(dbl2)
        If i2 > UBound(dbl2) Then
            dbl3(i1 + i2 - 1, 1) = dbl1(i1, 1)
            dbl3(i1 + i2 - 1, 2) = dbl1(i1, 2)
            i1 = i1 + 1
        ElseIf i1 > UBound(dbl1) Then
            dbl3(i1 + i2 - 1, 1) = dbl2(i2, 1)
            dbl3(i1 + i2 - 1, 2) = dbl2(i2, 2)
            i2 = i2 + 1
        Else
            If dbl1(i1, 1) < dbl2(i2, 1) Then
                dbl3(i1 + i2 - 1, 1) = dbl1(i1, 1)
                dbl3(i1 + i2 - 1, 2) = dbl1(i1, 2)
                i1 = i1 + 1
            Else
                dbl3(i1 + i2 - 1, 1) = dbl2(i2, 1)
                dbl3(i1 + i2 - 1, 2) = dbl2(i2, 2)
                i2 = i2 + 1
            End If
        End If
    Loop

    Sort2ArraysIn1_1 = dbl3
End Function

Code eingefügt mit Syntaxhighlighter 4.15
AnhangGröße
2 Arrays ineinander sortieren.xls48 KB
Sort2ArraysIn1.bas4.74 KB
Your rating: Keine