Sortieren

[Amateurprofi]

Das Sortieren von Daten ist in der DP, wie auch in anderen Foren, immer wieder ein beliebtes Thema.
Vor einigen Wochen hatte ich das Problem eine größere Datei (größer heißt ca 20 Milliarden Records) zu sortieren und suchte nach geeigneten Algorithmen.

Dabei machte ich die Erfahrung, daß quer durch alle Foren Sortierroutinen gezeigt werden, die hinten und vorn nicht funktionieren. BubbleSorts, die Exceptions auslösen, weil auf nicht existierende Felder des zu sortierenden Arrays zugegriffen wird, QuickSorts, bei denen ein Stacküberlauf eintritt und nicht funktionierende MergeSorts.

Als Beispiel mag der z.Z. in Wikipedia abgebildete Pascal Sourcecode für einen MergeSort gelten.
Er sortiert instabil (obwohl Stabilität bei einem MergeSort vorausgesetzt werden sollte) und er hat durch wiederholte Allozierung eines Hilfsarrays eine miserable Performance und benötigt unangemessen viel zusätzlichen Speicherplatz.

Ich nahm das zum Anlaß, mich etwas intensiver mit Sortieralgorithmen zu befassen.
Das Ergebnis ist das beigefügte Programm.
Es stellt verschiedene Versionen unterschiedlicher Sortierroutinen vor und bietet folgende Möglichkeiten an:

1) Performancetest
Beinhaltet die Messung des Zeitbedarfes der Routinen unter verschiedenen Ausgangsbedingungen, die Prüfung, ob wirklich korrekt sortiert wurde, die Prüfung, ob als stabil geltende Algorithmen tatsächlich stabil sortieren und, last not least, die Erfassung diverser statistischer Daten.

2) Graphische Darstellung des Sortiervorganges
Hierbei wird in einer 2D-Matrix die Veränderung des anfangs unsortierten Arrays auf dem Bildschirm dargestellt.

3) Schrittweise Verfolgung des Sortiervorganges
Hierbei werden das zu sortierende Array und ggfs. Hilfsarrays und die in der Routine benutzten Variablen auf dem Bildschirm dargestellt.
Der Sourcecode des Programmes wird in einer Listbox angezeigt und kann, wie mit einem Debugger, duchlaufen werden, was es erleichtert, die Funktionsweise zu verstehen.

Der beiliegende Help-File erklärt ausführlich alle Funktionen des Programmes und enthält auch die einzelnen Sourcecodes der Routinen sowie Erklärungen zur Funktionsweise. Letztere stammem aus unterschiedlichen Quellen wie Wikipedia, Brockhaus, DP etc. und sind entsprechend gekennzeichnet.

Ich hoffe, daß der eine oder andere Nutzen daraus ziehen kann.

Daß ich viel zu viel Aufwand mit diesem Programm getrieben habe, ist mir bekannt; ich brauche also keine diesbezüglichen Kommentare.
Hinweise auf Fehler sind dagegen willkommen....