Mein Beitrag

Mein Beitrag zu diesem Programm besteht aus folgenden Punkten:

  • Wandermerge, ein recht langsamer, dafür aber bedingt stabiler und  In-Situ -Verschmelzungsalgorithmus (implementiert beim Merge- und beim Naturalmergesort). Ich nannte ihn so, weil der sog. „Workspace“ sichtbar durch das Array wandert.
  • Einige wenige Verschmelzungsalgorithmen in diesem Programm funktionieren nur mit gleichgroßen (d.h., gleiche Elementeanzahlen) Teilarrays. Diese sind nur bei Mergesort mit Elementeanzahlen gleich einer Zweierpotenz gewährleistet. Damit diese Verschmelzungsalgorithmen für beliebig bzw. verschieden große Teilarrays und mithin auch für normales und Naturalmergesort nutzbar werden, entwickelte ich ein zunächst rekursives Unterprogramm zwecks Verschmelzungen („equalmerge“), das diese anspruchsvollen Verschmelzungsalgorithmen von verschiedengroßen Teilarrays abschirmt und diese mit nur gleichgroßen Teilarrays aufruft. Später transformierte ich dessen Rekursion noch in eine Iteration, wie ich es überall im Programm tat, um den Stackspeicher zu schonen. Die Funktionalität dieses Unterprogrammes kann ich nicht beweisen, aber bislang führte es seine Funktion fehlerlos aus.
  • Weiterhin stammt der Blocktauschalgorithmus „Kreuzindex“ in allen drei Geschwindigkeitsstufen von mir. Er funktioniert so, daß jedes Sortierelement vor dem Tausch seine Zielposition angeheftet bekommt. Der Rest ist mehr oder minder effizientes In-Situ-Umordnen.
  • Zuguterletzt stammen das einfache iterative Quicksort sowie einige Vereinfachungen und Modifikationen einiger Sortier- und Verschmelzungsalgorithmen von mir.

Kontaktformular