_ArraySortStable2D stabiler MergeSort für 2D-Arrays

  • Wie bereits in der SB bekannt wurde, ist der Sortieralgorithmus (insbesondere der für 2D-Arrays) in der Array.au3 bis zur 3.3.14.5 (ob das noch gefixt wird steht offen) nicht stabil.

    Das bedeutet, dass Einträge, welche den selben Schlüsselwert haben (der Vergleichswert) getauscht werden und so ihre vorherige Reihenfolge nicht behalten.


    Bei der UDF wird das 2D-Array mittels MergeSort sortiert indem man eine zu sortierende Spalte übergibt. Die Vertauschungen wirken sich auf die anderen Spalten ebenfalls aus und so hat man am Ende ein stabil sortiertes 2D-Array.

    Bei 1D-Arrays mag die Stabiltät eines Algorithmusses ja vielleicht egal sein, aber bei 2D-Arrays kann man damit wunderschöne Effekte erzielen um Daten zu sortieren.


    Beispiel:

    Man hat eine Tabelle (mit unsortierten Datensätzen) welche in der 1. Spalte die Postleitzahl und in der 2. Spalte den Namen einer Person beinhaltet.

    Sortiert man nun mit _ArraySortStable2D die 2. Spalte, so wird das Array in der 2. Spalte nun die sortierten Namen beinhalten (A-Z).

    Sortiert man anschließend wieder mit der UDF aber nun die 1. Spalte, so wird das Array in der 1. Spalte die sortierte Postleitzahl beinhalten, aber die 2. Spalte wird ihre relative Reihenfolge der Elemente, innerhalb der Postleitzahl, behalten.

    Man hat also am Ende ein Array mit der sortierten Postleitzahl (00000 - 99999) und in der 2. Spalte die Namen der Personen alphabetisch je nach Postleitzahl.


    Ein instabiler Algorithmus ignoriert diese Ordnung.


    Hier ein kleines Beispiel mit Früchten.

    Code
    1. #include <Array.au3>
    2. #include "_ArraySortStable2D.au3"
    3. Local $aTestArray[5][2] = [[5, "Cherry"], [4, "Banana"], [3, "Cherry"], [2, "Orange"], [1, "Apple"]]
    4. _ArraySortStable2D($aTestArray, 0)
    5. _ArrayDisplay($aTestArray)
    6. _ArraySortStable2D($aTestArray, 1, Default, Default, True)
    7. _ArrayDisplay($aTestArray)


    Dieses Mal sogar mit UDF-Header und Errorhandling :D


    Die Vergleichsfunktion ignoriert Groß- und Kleinschreibung! Es wird der Unicode-Wert verglichen, dabei gilt allgemeinerweise:

    Zahlen < Buchstaben < Unicode-Zeichen.