Icon Ressource

'FastSort' - Merge- bzw. Quicksort Hybriden für StarBasic (Libre-, OpenOffice) und VBA (MS Office) 1.0

Vor etwa einem Jahr hatte ich eine private Konversation mit einem Nutzer von LibreOffice. Seit 20 Jahren mach ich immer mal wieder was mit VBA, aber StarBasic ist doch etwas anders und die Dokumentation ist leider unterirdisch schlecht. Wie auch immer, entstanden sind ein paar Anwendungen, überwiegend Windows-spezifisch, die ich später veröffentlicht habe.
Dort auch enthalten, meine Implementierungen für Mergesort und Quicksort.



Zu Übungszwecken habe ich nun diese "FastSort" Lib noch einmal für VBA umgeschrieben. Passt natürlich nicht mehr zu den StarBasic Macros, ist aber zu schade um auf meiner Festplatte zu verrotten. Somit findet sich hier im Download eine leere Excel-Datei und eine leere Base-Datenbank (da LibreOffice Calc-Dateien mittlerweile inkompatibel mit OpenOffice sind) mit jeweils derselben öffentlichen API in VBA bzw. StarBasic.
Einzusehen ist der Code über das "Extras" Menü bzw. in der Regel auch per Tastenkombination [Alt]+[F11]. Im ReadMe Modul finden sich Informationen zur MIT Lizenzierung, Kurzinformationen zu den Prozeduren, sowie eine Anleitung wie sich die API erweitern lässt. Das Unit_Tests Modul enthält Test- und Beispielaufrufe.

Die Prozeduren sortieren 1D Arrays, 2D Arrays und Jagged Arrays (Arrays von Arrays), standardmäßig für numerische Typen und Strings (Groß- und Kleinschreibung beachtend oder wahlweise ignorierend).
Speziell für Windows gibt es die Möglichkeit Strings logisch/natürlich zu sortieren, unter Verwendung derselben Win32 API Funktion (StrCmpLogicalW), die auch für den Windows Explorer genutzt wird um Dateinamen sortiert anzuzeigen. Dabei werden Zahlen in Strings numerisch ausgewertet, statt als Text. Beispiel: Im logischen Vergleich ist "a2b" < "a100b" (da Zahl 2 < Zahl 100), in einem normalen Textvergleich ist "a100b" < "a2b" (da Zeichen '1' < Zeichen '2').

Der Mergesort Algorithmus ist stabil implementiert. Heißt, die ursprüngliche Reihenfolge von Elementen mit gleichem Sortierschlüsselwert bleibt erhalten. Das ist mglw. bei mehrdimensionalen und Jagged Arrays von Interesse, sobald sie mehrfach mit unterschiedlichen Schlüsseln sortiert werden.
Der Quicksort Algorithmus ist von Natur aus instabil. Er hat aber durchschnittlich eine minimal bessere Performance und benötigt weniger Speicher.
Beide Algorithmen arbeiten rekursiv.
Optimierungen: Hybriden mit Insertionsort werden verwendet um das Overhead von reinem Merge- bzw. Quicksort für kurze Teilarrays zu vermeiden. Beim Mergesort werden sortiert aneinander liegende Teilarrays übernommen, ohne den Merging Prozess zu durchlaufen.
Aber: Insbesondere für das lediglich interpretierte StarBasic scheint es nicht sinnvoll zu sein die Algorithmen mit Optimierungen zu überladen. Alle möglichen Sonderkonstellationen zu behandeln würde für "durchschnittlich unsortierte" Arrays dann eher einen Performance Drop erzeugen. Außerdem soll der Code les- und erweiterbar bleiben. Eine bis ins Detail ausgeklügelte Mergesort Hybride à la Timsort wird man hier also nicht finden.



Fun Facts:
StarBasic ist, im Gegensatz zu VBA, nicht vorkompiliert. Im Vergleich ist StarBasic somit ca. 30x langsamer als VBA (was vermutlich der Grund ist, warum Open- und LibreOffice eher auf Python als Macro-Sprache setzen). Um so erstaunlicher ist, dass sowohl Open- als auch LibreOffice von jeher mit einer Bubblesort (🙈) Prozedur in der Tools Lib ausgeliefert werden. LibreOffice kommt ab Version 7.1 mit den ScriptForge Libs, wo eine Heapsort Funktion existiert. Die ist immerhin 30% schneller als die alte Bubblesort Subroutine, aber immer noch fast 10x langsamer als die Quick- und Mergesort Prozeduren die ich hier veröffentliche. Zugegeben war ich ziemlich offensiv performancegetrieben unterwegs und mache keine Prüfungen der Parameterwerte (wer Mist übergibt bekommt Mist zurück, bestenfalls eine Exception). Trotzdem ist das ziemlich enttäuschend, zumal Heapsort nicht einmal stabil sortiert.
  • Like
Reaktionen: Mat
Autor
german
Downloads
15
Aufrufe
61
Erstellt am
Letzte Bearbeitung
Bewertung
5,00 Stern(e) 1 Bewertung(en)

Weitere Ressourcen von german

Aktuellste Rezensionen

Ich war auch negativ überrascht von fehlenden/schäbigen Sortierverfahren, als ich das letzte Mal mit VBA Makros zu tun hatte. Nächstes Mal wird deine Library direkt rein gepackt 😀
Oben Unten