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....

[TheAn00bis]

Wow, das Programm ist echt stark!

Schön fände ich eine kleine Beschreibung zu den einzelnen Algorithmen, insbesondere die Unterschiede zwischen den verschiedenen Alogorithmen gleichen Typs (z.B. Quicksort 1-4). Natürlich kann man sich auch den Quellcode anzeigen lassen, aber bis man dort die gravierenden Unterschiede entdeckt hat dauert das sicher etwas.
Dein Programm kann man bestimmt sehr gut gebrauchen, wenn man sich mal ausführlicher mit dem Sortieren von Daten beschäftigen möchte.

Außerdem wäre es schön, wenn du Testergebnisse mitliefern würdest, denn den Performance-Test für alle Algorithmen durchlaufen zu lassen dauert ziemlich lange.

Edit: Gerade erst entdeckt, vorbildliche Hilfe!

[Amateurprofi]

Hallo, TheAnOObis,
Danke.
Im HelpFile ist die generelle Arbeitsweise eines QuickSort erklärt.
Mit Menu > Hilfe öffnest Du den HelpFile.
Im HelpFile auf der Inhaltsseite klicke die vorletzte Zeile "Source Codes und Beschreibungen..."
Dann bist Du auf einer Seite, die eine Liste der Source Codes enthält.
In einer der Zeilen QuickSort_0 bis QuickSort_2 klicke auf Arbeitsweise - Du landest dann immer auf der selben Seite, die die generelle Arbeitsweise von Quicksort erklärt.
Die Unterschiede der einzelnen Algorithmen sind eigentlich nur gering und sind auf den Seiten mit den SourceCodes, zugegebenermaßen etwas knapp, kommentiert (ich hatte einfach keine Lust mehr.....)

Und wenn Du Dir eine Statistik erstellen willst, zum Beispiel für alle Routinen und alle verschiedenen Füllmodi und für verschiedene Anzahlen dann kannst Du das zum Beispiel so machen:
Klicke Menu > Performancetest.
Im Einstellungen Dialog gib ein
Anzahl Min = 10
Anzahl Max = 1000
Anzahl Faktor = 10
Erster Index = 1
Unter Füllmodus klicke das Wort "Füllmodus" (wenn dann alle Checkboxen unmarkiert sind, klicke noch einmal auf "Füllmodus", dann sollten alle Modi (bis auf die beiden letzten) gecheckt sein.
In der Listbox mit den Algortithme selektiere alle.
In der Gruppe Optionen wähle die Optionen, die Dir zusagen.
Abschließend klicke den Button "Erstellen" und es sollte nicht mehr als 15 Sekunden dauern, bis du ca. 1000 Zeilen in der Statistik Listbox hast.
Bei größeren Anzahlen dauert es natürlich etwas länger, insbesondere, wenn Du unter Optionen die Checkboxen "Vorgänge Zählen" und "Stabilität prüfen" gecheckt und auch die langsamem Algorithmen (alles was über den ShellSorts steht) ausgewählt hasr.
Die schnelleren Algorithmen sind aber auch bei 100000 oder auch 10 Mio noch recht flink.
Vorsicht ist geboten bei QuickSort_0 und MergeSort_0 weil die bei großen Anzahlen Probleme machen (ggfs auch Exceptions). Darum sind die im Helpfile auf den Seiten mit den Source Codes als abschreckende Beispiele deklariert.
Noch ein Tip : Im Menu Statistik markiere den Eintrag "Automatisch speichern", dann wird die Statistik gespeicher und wird beim nächsten Programmstart automatisch wieder geladen.
Viel Spaß damit.

[stoxx]

Hi Amateurprofi,

das ist ja richtig was für Studenten

zum compilieren fehlt leider die Sort_05.pas und Sort_06.pas.
Das Programm hast Du aber nicht heute innerhalb eines Tages erstellt oder ? .. ähm

Kennst Du das hier ? zwar bei weitem nicht so schön wie Deins, aber dennoch auch was funktionierendes.

http://www.thedelphimagazine.com/disks/dmag37.zip


Ist Dein Postfach eigentlich voll, weil Nachrichten nicht übermittelt werden ?
bis dahin ...

[Amateurprofi]

Hallo Stoxx,

Zitat:

zum compilieren fehlt leider die Sort_05.pas und Sort_06.pas.

Ich dachte, daß die .dcu Dateien dafür ausreichen müßten. scheint aber wohl nicht so zu sein.
Sort_05.pas enthält nur eine einzige Konstante, nämlich ein Array of Strings, das die Source Texte für die Verfolgung des Sortierbedarfes enthält.
Sort_06.pas enthält den ganzen Schrott der für graphische Darstellung und Verfolgung der Sortiervorgänge enthält. Aus dieser Unit heraus wird auch auf andere Units zugegriffen, vermutlich reicht deswegen die .dcu nicht aus.

Zitat:

Das Programm hast Du aber nicht heute innerhalb eines Tages erstellt oder ? .. ähm

Nein.

Zitat:

Kennst Du das hier ? zwar bei weitem nicht so schön wie Deins, aber dennoch auch was funktionierendes.
http://www.thedelphimagazine.com/disks/dmag37.zip

Nein, kannte ich nicht.
Interessant fand ich in "VisualBestInsertionSort" die Idee, zunächst das kleinste Element zu suchen um dann in der While Schleife nicht mehr prüfen zu müssen ob der Index am unteren Ende ist. Bringt aber nur bei großen Anzahlen einen Vorteil, dagegen bei kleinen Anzahlen kostet das zu viel Zeit und verschlechter die Performance sehr. Da man einen InsertionSort wohl für kleine Anzahlen einsetzen wird ...

Zitat:

Ist Dein Postfach eigentlich voll, weil Nachrichten nicht übermittelt werden ?

Nein. Zu ca. 25 % gefüllt.

[Phoenix]

Wie cool

Ich müsste nochmal in mein Script zu Sortieralgorithmen gucken, irgendwo haben wir sogar rechnerisch mal bewiesen dass Quicksort der schnellste und effizienteste Algorithmus ist, es wäre vielleicht ned schlecht, ein wenig Hintergrund-Theorie auch noch mit an den Mann zu bringen

[r2c2]

Hallo,
hab momentan nicht besonders viel Zeit zum Testen. Trotzdem noch n paar Anmerkungen, die ich schon jetzt bringen kann:
- Fenster könnt resizable sein
- Das Menü könnte man etwas standardkonformer machen: Datein, Bearbeiten, ... oder so ähnlich. Hab jetzt schon n paar mal auf Ende gedrückt, weil ich gucken wollte, was so in den Menüs steht
- die Dialoge müssen nicht unbedingt maximierbar sein...
- Systemspezifische Standard-Farben wären praktisch. Oder nimmst du absichtlich clGray?
- Hints machen das ganze etwas übersichtlicher
- Es gibt keine Möglichkeit die Statistik anders zu sortieren, wenn man man angefangen hat auf die Collumnheaders zu klicken(einziger Ausweg bildet was Hauptmenü)
- ...

Alles in Allem nur kleinkram(also nicht dein Prog, sondern nur meine Anmerkungen ). Wenn ich wieder mehr Zeit hab, werd ichs vielleicht auch ausführlicher testen...

Zitat von Phoenix:

Wie cool
Ich müsste nochmal in mein Script zu Sortieralgorithmen gucken, irgendwo haben wir sogar rechnerisch mal bewiesen dass Quicksort der schnellste und effizienteste Algorithmus ist, es wäre vielleicht ned schlecht, ein wenig Hintergrund-Theorie auch noch mit an den Mann zu bringen

Ich hab zu dem Thema ne Facharbeit geschrieben(und kürzen müssen, weil se zu lang war...). Wenns jemand interessiert, kann er sich se ja mal angucken. Ich häng mal die ungekürzte Fassung an...

mfg

Christian

[Amateurprofi]

Hallo, Christian,
Danke für Deine Kommentare.

Zitat:

Fenster könnt resizable sein

Ja. Hab ich aber bewußt so gemacht, daß die komplette WorkArea ausgefüllt wird.

Zitat:

Das Menü könnte man etwas standardkonformer machen: Datein, Bearbeiten, ... oder so ähnlich. Hab jetzt schon n paar mal auf Ende gedrückt, weil ich gucken wollte, was so in den Menüs steht

Ich mag die Standards nicht, bzw. ich setzé meine eigenen Standards und zu denen gehört das Ende/Exit MenuItem. Allerdings schreibe ich meine kleinen Progrämmchen in der Regel nur für mich. Für solche Programme die ich veröffentliche sollte ich mich mehr an Standards halten - da gebe ich Dir Recht.

Zitat:

die Dialoge müssen nicht unbedingt maximierbar sein

Ja, hab ich nicht dran gedacht.

Zitat:

Systemspezifische Standard-Farben wären praktisch. Oder nimmst du absichtlich clGray?

Ja, ich nehme bewußt clGray,clSilver etc.

Zitat:

Hints machen das ganze etwas übersichtlicher

Wollte ich eigentlich machen, hatte aber irgenwann einfach keine Lust mehr.

Zitat:

Es gibt keine Möglichkeit die Statistik anders zu sortieren, wenn man man angefangen hat auf die Collumnheaders zu klicken(einziger Ausweg bildet was Hauptmenü)

Doch. Du kannst die Listbox nach allen sichtbaren Kriterien sortieren und auch nach mehreren und aufwärts oder abwärts. Gerade das war für mich (in einem Programm, daß sich mit Sortieralgorithmen beschäftigt) ein wichtiger Punkt.
Schau mal in die Hilfe unter "Das Header Control". Auch im Kapitel "Die Statistik" wird darauf verwiesen.

Edit:
Deine Facharbeit habe ich mir runtergeladen.
Hab schon mal kurz reingeschaut - aber dafür muß ich (und werde ich) mir mal sehr viel Zeit nehmen.

[r2c2]

Zitat von Amateurprofi:

Zitat:

Fenster könnt resizable sein

Ja. Hab ich aber bewußt so gemacht, daß die komplette WorkArea ausgefüllt wird.

Was für n Glück das ich auch ne 1027*786er Auflösung hab. Stell dir aber mal vor irgendwer muss mit ner 800*600er arbeiten... Warum nimmst du nicht einfach alClient?

Zitat:

Zitat:

Es gibt keine Möglichkeit die Statistik anders zu sortieren, wenn man man angefangen hat auf die Collumnheaders zu klicken(einziger Ausweg bildet was Hauptmenü)

Doch. Du kannst die Listbox nach allen sichtbaren Kriterien sortieren und auch nach mehreren und aufwärts oder abwärts. Gerade das war für mich (in einem Programm, daß sich mit Sortieralgorithmen beschäftigt) ein wichtiger Punkt.
Schau mal in die Hilfe unter "Das Header Control". Auch im Kapitel "Die Statistik" wird darauf verwiesen.

Was ich eigentlich gemeint hab, ist folgendes:
- Klick auf "Algorithmus" --> es wird danach sortiert
- Klick auf Anzahl --> es wird nach Anzahl und dann nach Algorithmus sortiert
- Ähm... jetzt wollt ich mich doch mal umentscheiden. Besser zuerst nach Algorithmus und dann nach Anzahl
--> einzige Möglichkeit: Sortierung löschen(Klick auf die letzte Spalte oder über das Menü) und wieder neu klicken

Ich würde das folgendermaßen lösen(und auch das wäre wieder etwas "standardkonformer"...):
- Einfach-Klick zum Priörität-1-Sortieren
- Priorität-2 wird wird durch Strg+Klick gemacht
--> so kann man dann einfacher Sortieren ohne extra löschen zu müssen

*mal wieder auf die Uhr guck und wider erschreckt wie spät es ist*
Sry, muss noch n referat für Deutsch fertig machen. Irgend was wollt ich noch sagen, hab aber jetzt keine Zeit mehr nachzudenken, was das war...

mfg

Christian

[Amateurprofi]

Zitat von r2c2:

Was für n Glück das ich auch ne 1027*786er Auflösung hab. Stell dir aber mal vor irgendwer muss mit ner 800*600er arbeiten... Warum nimmst du nicht einfach alClient?

Das hatte ich ursprümglich so gemacht, fand es so aber besser. Ich arbeite mit 1280x1024 habe aber die Breiten der Listbox Spalten so bemessen, daß auch bei einer Breite von 1024 alle Spalten der Listbox sichtbar sind. Stelle doch spaßeshalber Deine Auflösung auf 800*600 und starte dann das Programm. Dann sollten die Spalten, die hinten liegen nicht gezeigt werden. Mit einer horzontal scrollbaren Listbox wollte ich mich nicht befassen. Ich gebe Dir insofern recht, daß das professioneller wäre. Aber, wie mein Intro sagt, bin ich nur ein Amateurprofi. Das Thema hab ich übrigens im Helpfile explizit erwähnt (was zeigt, daß ich mir dessen bewußt war) und auch alternativen erwähnt, nämlich speichen als CSV-File und Hochladen in z.B. Excel.

Zitat:

Ich würde das folgendermaßen lösen(und auch das wäre wieder etwas "standardkonformer"...:wink:):
- Einfach-Klick zum Priörität-1-Sortieren
- Priorität-2 wird wird durch Strg+Klick gemacht
--> so kann man dann einfacher Sortieren ohne extra löschen zu müssen

Auch das war ursprümglich so ähnlich gelöst. Hab mich dann aber so entschieden, daß, wenn eine bereits sortierte Spalte geklickt wird, diese ihre Priorität innerhalb der Gesamtsortierung beibehalten wird. Und was Standards betrifft. Wie geht das denn in Standard Anwendungen wie z.B Excel oder auch dem Explorer? Bei letzterem wird (bei mir zumindest) nur nach der zuletzt geklickten Spalte sortiert. Ich denke mal jeder hat seine persönlichen Meinungen, wie es optimal wäre.

Auch wenn ich in einigen Punkten anderer Meinung bin als Du, nehme ich Deine Kommentare durchaus zur Kenntnis und werde bei zukünftigen Programmen über Alternativen zu meinen Ansichten nachdenken. Deshalb Danke.