Hallo Delphianer und vor allem diesmal konkret Sortierfreunde!
Es ist mal wieder soweit, hier ist das Ergebnis meiner Hobbyprogrammiererei der letzten Monate: Visualisierte (oder noch genauer: animierte) Sortieralgorithmen.
Bekannt sind diese Algorithmen natürlich (und das Thema mag so mancher als abgedroschen empfinden), jedoch gefiel mir die graphische Umsetzung derselben, die ich bislang fand, nicht.
So wird zum einen oft der Bildschirm nicht ausgenutzt, was die mögliche Elementanzahl verringert. Zum anderen halte ich Balken-/Liniendarstellungen für prägnanter als schnöde Pixel. Dann liegen oft nur Zufallspermutationen (einer aufsteigenden Menge) oder Zufallszahlen als zu sortierende Startmengen zugrunde. Das alles habe ich etwas erweitert, um ein wenig „Kinogefühl“ aufkommen zu lassen. Die Bedienung des Programmes ist m. E. so simpel und intuitiv möglich, daß es nicht weiter beschrieben werden muß.
Mein Interesse lag zuvörderst bei solchen Sortieralgorithmen, bei denen die Visualisierung wenigstens halbwegs erkennen läßt, was intern abläuft. Die temporäre Nutzung zusätzlichen Speichers wie bei den klassischen Mergesorts und bei den Bucketsorts wird nicht visualisiert, sondern eben nur das, was in und mit der „Hauptmenge“ geschieht. Desweiteren beschränkte ich mich wegen der Darstellungsorientierung auf die Sortierung linearer, d.h. eindimensionaler Datenmengen, also Arrays (die Werte werden, entsprechend ihrer Größe, natürlich als verschiedenlange Balken dargestellt).
Einbezogen habe ich alle Komplexitätsklassen dieser Algorithmen, was sich auch in der Laufzeit bemerkbar macht, ohne jedoch die Algorithmen nach Komplexitätsklasse vorzuselektieren oder zu ordnen (nur alphabetisch nach Namen). Eingeweihte wissen ohnehin bescheid. Das wären:
- Die absolute Katastrophe: Erst (jeweils zwei Elemente) tauschen, dann die gesamte Elementemenge auf Sortierheit prüfen. Doch auch diesem Vorgehen ist letztlich die Systematik nicht abzusprechen und führt - genug Zeit und Ausdauer vorausgesetzt - irgendwann sicher zum Ziele. Ich empfehle aber, für den Sortiererfolg es mit Elementeanzahlen maximal 10 zu versuchen, dann wird das Darstellungsfenster aber sehr klein. Vertreter: Bogo- und Bozosort.
- Von der Laufzeit her schon um Größenordnungen besser, aber immer noch grottenschlecht sind bestimmte rekursive Algorithmen: Slow- und Trippelsort.
- Die klassischen („elementaren“) Algorithmen, die letztlich, im maximalen Fall, jedes Element mit jedem (anderen) vergleichen (mit der Elementeanzahl quadratisch wachsende Vergleichsanzahl) und bei Bedarf tauschen (so z.B. Bubble-, Insertion-, Oet- und Shakersort). Ein wenig aus dem Rahmen fallen Selektion- und Plaselsort, die zwar auch zu dieser Klasse zählen, jedoch geschickterweise die Anzahl der Vertauschungen auf das nötige Maß minimieren, so daß deren tatsächliche Geschwindigkeit bei den im Vergleich zu in der Praxis zu sortierenden Mengen nur erklecklichen Elementeanzahlen, die Bildschirmspalten zulassen, erstaunlich hoch ist.
- Verbesserte, d.h. asymptotisch gute Algorithmen wie z.B. Shell-, Gap- und Shearsort.
- Asymptotisch optimale Sortieralgorithem wie z.B. Quick-, Heap- und Mergesort. Vom Heapsort habe ich Dijkstras Smoothsort und von den diversen Mergesorts auch bitonische und Varianten mit iterativen „In-Place“-Veschmelzungen dabei (die benötigen also kaum zusätzlichen Speicherplatz, vor allem keinen Stack), s.u. .
- Die schnellsten Algorithmen sind spezielle Sortieralgorithmen (Bucketsorts), kommen ohne Vergleiche aus, setzen jedoch voraus, daß die Anzahl der möglichen Werte endlich ist (das ist z.B. bei Integervariablen der Fall): Beadsort, Distribution Counting und - mit deutlichen Abstrichen wegen mehrerer, bitbezogener Schleifendurchläufe - Strait Radix Sort.
Als Schmankerl habe ich optional bei Mergesort und Naturalmergesort das “In-Place-Mergen” nach der Idee Siegfried Sielaffs („Simplewapsort“) implementiert, mich jedoch mit der Rekursion desselben nicht zufriedengegeben, sondern es nach der Idee Robert Sedgewicks analog seinem Quicksort iterativ umgestaltet, wobei ein eigens dafür genutztes Datenfeld namens Stack letztlich den Stack emuliert und der deshalb als Namenspatron herhalten mußte, jedoch deutlich weniger (Haupt-)Speicher, als was vom Stack benutzt würde, verbrauchen und zudem laufzeitgünstiger sein dürfte:
Somit enthält mein Programm einen Sortieralgorithmus, der bei dem heutigen Softwareniveau (meine ich positiv!) als optimal angesehen werden kann:
- allgemeingültig i.d.S., daß alle Werte (und eben nicht nur integre) können sortiert werden,
- stabil (d.h., wertgleiche Elemente werden nicht vertauscht, deren ursprüngliche Reihenfolge bleibt also im Verlaufe der Sortierung enthalten),
- (vermutlich, wäre noch nachzuweisen) laufzeit- bzw. geschwindigkeitsoptimal (n*log(n)), vielleicht aber doch nur asymptotisch gut analog Bitonic Sort,
- „intelligent“ genug, (vor-)sortierte Mengen zu „erkennen“, indem er darauf mit einer Laufzeitverkürzung „reagiert“,
- nur iterativ, keine Rekursion und
- (fast) kein zusätzlicher Speicher wird benötigt, insbesondere der etwas heikle Stack wird geschont.
All' diese Eigenschaften besitzt das Natural Mergesort mit dem iterativen In-Situ-Verschmelzen.
Die langsam(st)en Algorithmen lassen sich mit ESC abbrechen, während die optionale Bremse bei den schnell(st)en Algorithmen eingefügt wurde. Wessen Computer andere Geschwindigkeiten hat/haben, der kann und möge das natürlich entsprechend anpassen, Quelltexte liegen ja mit bei.
Angefangen hatte ich mit Delphi-2 (igitt), bei dem die Arrays im Quelltext entsprechend den einmal einzugebenden Bildschirmkoordinaten (bei mir 1600x1200) vor der Compilierung statisch zu dimensionieren sind. Das ist natürlich völlig veraltet, so daß ich in Richtung Delphi 4 aufbohrte: Eines mit einmaliger Arraydimensionierung während des Startes und eines, das die Arrays entsprechend der eingestellten Darstellungsfenstergröße automatisch während der Laufzeit anpaßt (was aber nicht optimal sein soll).
Meine wichtigsten Quellen der Algorithmen waren das Werk „Algorithmen und Datenstrukturen“ von Robert Sedgewick sowie die sehr umfangreiche Internetseite zu Sortieralgorithmen von Peter Weigel:
http://home.arcor.de/peter-weigel/sortieralgorithmen (die schaltete er dankenswerterweise privat wieder frei, nachdem die von ihm vor einigen Jahren abgegebene
http://www.sortieralgorithmen.de seit Monaten nicht mehr erreichbar ist). Zusätzlich fand ich im Internet noch die eine und andere gute Idee. Von mir stammen nur die trivialen Varianten (nicht das Original) des Bozosorts sowie die Nach-Delphi-Portierung des In-Place-Mergens. Deshalb ist das Programm natürlich komplett frei. Sollte noch jemand eine gute Idee für einen visualisierungswerten Algorithmus haben, dann her damit, oder er baut ihn sich selbst ein.
Trotz aller akribischer Proben und Kontrollen kann ich bei Programmen dieser Größe Fehler leider nicht ausschließen, würde mich aber über diesbezügliche Rückmeldungen dankend freuen.
Auch als Demonstrationsprogramm z.B. für den Informatikunterricht kann ich mir dieses Programm gut vorstellen. Zudem sind Sortieralgoritmen die im wahrsten Sinne des Wortes offensichtliche Widerlegung der immer noch zu findenden pauschalen und damit falschen Behauptung, Algorithmen seien „Rechen- bzw. Berechnungsvorschriften“.
Kleiner Tip: Swirlsort mit der Werteerzeugung "natürliche Zahlen (je einmal) und der Startmengenstruktur „Aufsteigend, größtes Element vorn“ starten - ich wette, daß so etwas noch niemand von Euch je gesehen hat!
Viel Spaß!
Delphi-Laie
Edit: Neue Version(en) mit weiteren sechs verschiedenen Startmengen unterschiedlichen Ordnungsniveaus hochgeladen.
Edit 2: Einen großen und mehrere kleine Fehler behoben; die Bremse funktioniert jetzt bei allen Algorithmen.
Edit 3: Swirlsort korrigiert, funktioniert jetzt auch mit Zufalls- und Konstantzahlen.
Edit 4: Splitsort zeigt gegenüber zuviel teilgeordneten (höheres Ordnungsniveau als Zufall) Startmengen ein zu ungünstiges (quadratisches?) Laufzeitverhalten, deshalb „Aufnahme“ in die Menge der abbrechenbaren Algorithmen.
Edit 5: Gültigkeitsbereich dreier Graphikprozeduren von global in lokal verändert: In aufrufende Prozedur verschoben.
Edit 6: 4 weitere Startmengen hinzugefügt; die (Maximal-)Auflösung in der undynamischen (D2&3-)Variante auf WUXGA 16:10 (1920*1200) erhöht.
Edit 7: Fehler bei der Spaltenanzahlzuordnung weniger Startmengen beseitigt.
Edit 8: Das einfache (rekursive) Mergesort war kein stabiler Sortieralgorithmus, jetzt „stablisiert“ und zudem einen effizienteren Ansatz mit der temporären Auslagerung nur eines Teilarrays gewählt (nach
Mergesort vom ITI der FH Flensburg).
Edit 9: Kleine Fehler beseitigt.
Edit 10: Kleinen, aber fatalen Fehler in Mergesort bereinigt (< statt <= bewirkte inverse Sortierreihenfolge bei konstanten Elementen (also Instabilität, inverse Stabilität sozusagen).
Edit 11: Beide Quicksorts beschleunigt: Tausch nur noch nach Elementevergleich. Damit vermischen beide Algorithmen gleichgroße Elemente auch nicht mehr unkontrolliert, sondern werden wenigstens „invers stabil“ (=bei gleichgroßen Elementen wird deren Reihenfolge invertiert).
Edit 12: Borderstyle vom Sortierformular so geändert, daß es nunmehr ein echtes Fenster (also mit Rahmen) ist. Mit dem Setzen des Formstyles des Sortierformular auf fsStayOnTop sollen zudem die störenden Neuzeichnungen anzahlig zurückgedrängt werden.
Edit 13: Subtilen Fehler bei der Bestimmung der maximalen Spalten- und Zeilenanzahl im Fenstermodus beseitigt (?). Funktionierte nicht richtig, nachdem das Formular 2 (zum Sortieren) schon mal visible war bzw. benutzt wurde.
Edit 14: Insertionsort beschleunigt (zyklisches Verschieben anstatt häufigen Vertauschens). 2 weitere Insertionsorts hinzugefügt (Variante 3 zeigt ziemlich selten einen nicht reproduzierbaren Fehler). Das Sortierformular, sofern als Fenster benutzt (also mit Rahmen), behält nunmehr seine Position, zu der es verschoben wurde (vorher immer Bildschirmzentrierung desselben).
Edit 15: Subtilen Fehler bei der Generierung der Startmenge „2 separate absteigende Teilmengen“ korrigiert. Dynamische Längenanpassung der (zu sortierenden) (Haupt-)Menge korrigiert.
Edit 16: Farb- und Schwarz(-Weiß)-Varianten beider Programme verein(ig)t.
Edit 17:
- Neuzeichnen der zu sortierenden Menge dank eines zusätzlichen Threads nun auch während des Sortierens möglich,
- Abbruchverhalten korrigiert, verfeinert (jeder Mausklick und/oder Tastendruck) und verbessert,
- Stayontop-Verhalten des Sortierformulars mit ereignisausgelöstem BringToFront verbessert und
- alle 4 Simple-/Naiselsorts sind nunmehr abbrechenbar.
Edit 19:
- AVL- & B-Sort (je in- & out-of-place) sowie Pancakesort hinzugefügt.
- Prozeß- und Threadpriorität(en) massiv erhöht, um eine möglichst flüssige Darstellung (sonst oft unregelmäßige Ablaufgeschwindigkeit) zu gewährleisten. Die Bedienbarkeit des Programmes (konkret Abbrechenbarkeit der langsam(st)en Algorithmen) bleibt dabei erhalten.
Edit 21: Programmhauptformulartitelzeile erweitert. Der Neuzeichnenprozedur in den D4-Programmvarianten das irrtümlich fehlende "BringToFront" hinzugefügt.
Edit 22: Shell- mit den beiden Shearsorts für eine alphabetisch korrekte Reihenfolge vertauscht.
Edit 23: Meldung über Anpassung der Spaltenanzahl an eine 2er-Potenz (bei 2 Sortieralgorithmen) in den Vordergrund geholt, damit diese „wegklickbar“ ist. Fenster„handhabung“ in jener Prozedur (zur Anpassung der Spaltenanzahl an eine 2er-Potenz) verbessert.
Edit 24:
- Delphi-2-/-3-Variante jetzt mit bis zu 2048 Elementen (Spaltenanzahl der QXGA-Auflösung) möglich.
- Anzeige der Schleifenanzahl bei Bogo- und Bozosort jetzt nach dem Endpiepton.
Edit 25: Kleine Fehlerbereinigungen:
- Neuzeichnen immer ohne Bremsverzögerung
- Zentrierung bei Spaltenanzahlanpassung auch bei Fensterformular (also eines mit Rahmen, Formstyle<>bsnone)
Edit 26: Kleine Fehlerbeseitigungen:
- Anpassung der Spaltenanzahl an 2er-Potenz verbessert
- Showmessage beim vereinfachten Plaselsort jetzt sichtbar
Edit 27: Formular 2 (für die Sortierdarstellung) nunmehr immer zentriert.
Edit 28: Showmessage für Schleifenanzahlszähler nunmehr immer im Vordergrund.
Edit 29:
- Quelltexte bereinigt (insbesondere überflüssige (ungenutzte) Variablen entfernt)
- Sortieralgorithmus hinzugefügt (MinMax(Selection)Sort)
- 4 neue, weitere Startmengen hinzugefügt
- Swirlsort beschleunigt
- Lazarus-/FPC-Pendants der Quelltexte erstellt und hinzugefügt
Edit 30: Vorsortierbarkeit (mit Shellsort oder binär) der Startmengen mit variabler (Vor-)Sortierschleifenanzahl hinzugefügt. Kleinere Quelltextverbesserungen.
Edit 31:
- Zwei Dreifarbmodi hinzugefügt
- Generelle Spiegelbarkeit der Startmengen hinzugefügt, damit konnten einige Startmengen entfallen
- kleine Fehlerbeseitigungen
Edit 32: Darstellung der speziellen Sortieralgorithmen nur noch mit schwarzen Balken, um Irritationen und Fehlervermutungen zu vermeiden. Diverse Fehlerbereinigungen und Detailverbesserungen.
Edit 33: Diesmal nur Verbesserungen „unter der Haube“:
- Zufallspermutationserzeugung nach dem Fisher-Yates-Algorithmus
- Farbberechnung der Linien effektiver (nicht erst bei der Ausgabe, sondern schon bei der Erzeugung der Startmengen)
Edit 34:
- Fehler, der die zweifarbige Darstellung verhinderte, beseitigt.
- Prozedur, die bei bestimmten Sortieralgorithmen die Anzahl der Sortierelemente an eine Zweierpotenz anpaßt, überarbeitet (fehlerbereinigt, verbessert und erweitert).
- Sortieralgorithmus „Skiplistsort“ hinzugefügt (Grundlage waren die Datenstrukturen und zugehörigen Unterprogramme der Unit „csFasterSkipLists“ in alzaimars Programm „testlists“, die zu übernehmen er mir dankenswerterweise gestattete; die originale Quelle dazu soll ftp://ftp.cs.umd.edu/pub/skipLists/) sein. Leider ist auch hier wieder nichts davon zu erkennen, wie er intern funktioniert. Er arbeitet allerdings sehr schnell und könnte mithin auch zu den „asymptotisch optimalen“ Sortieralgorithmen gehören.
Edit 35: Anzeige des Schleifenzählers bei den langsamsten Algorithmen nach Sortierende oder -abbruch nunmehr optional.
Edit 36:
- Überflüssige Aufrufe der Prozedur „Mischen“ entfernt.
- Prozedur „Zweierpotenzanpassung“ nochmal überarbeitet (kleine Fehler beseitigt).
Edit 37: Skiplistsort überarbeitet.
Edit 38: Smoothsort überarbeitet:
- marginal vereinfacht und beschleunigt (for- statt while-Schleifen, zwei anscheinend überflüssige Bedingungsabfragen entfernt (auskommentiert)).
- soweit angepaßt, daß dieser Algorithmus - bei anderweitiger Verwendung - mehr als ca. 7 Mio. Elemente (32. Leonardozahl) sortieren kann. Dazu müssen einige Variablen 64-Bit-Breite haben.
Edit 39: Kleine Fehlerbereinigungen.
Edit 40: Das komplexere Swapmergen (Swapsort nach Siegfried Sielaff) für Merge- und Natural Mergesort hinzugefügt.
Edit 41: Beim klassischen Mergesort die Rekursion und damit Stackbenutzung entfernt. Die Verwaltung/„Handhabung“ des Pseudstacks (Stackemulation) überarbeitet/verbessert.
Edit 42: Bitonic Mergesort 2 (=bitonisches Natural Mergesort) korrigiert.
Edit 43: Bubblesort verbessert (effizienter gestaltet): zyklische Verschiebungen statt Vertauschungen.
Edit 44: Fehler in den Lazarusversionenen dieser Sortierprogramme beseitigt: Bogosort 2 zählte seine Schleifen(durchläufe) nicht.
Edit 45:
- Sortieralgorithmen hinzugefügt:
- Buttom-Up-Heapsort
- n-Heapsort
- für das Merge- und das Naturalmergesort die In-Situ- (oder: In-Place-)Verschmelzungen nach Jason Harrison sowie nach John Ellis und Minko Markov)
- Die Farbgradienten sind jetzt auch für die Zielmenge(n) einstellbar (vorher nur für die Startmenge(n))
- Einige Detailänderungen und Fehlerbereinigungen.
Edit 46:
- Sortieralgorithmen hinzugefügt:
- Heap-F-Sort
- Mergesort mit einfachem und komplexem In-Situ-Verschmelzen nach HP-/SGI-Standard-Template-Library
- Invertieren der Startmenge jetzt vor und nach evtl. Vorsortierung möglich.
- Kleine Fehlerbereinigungen.
Edit 47: (Abschaltbare) Meldung wegen der nur schwarzen Linien bei den speziellen Sortieralgorithmen hinzugefügt. Kleinere Fehlerbereinigungen.
Edit 48:
- Odd-Even-Mergesort (eigentlich ein klassisches rekursives Mergesort mit Odd-Even-Merge) hinzugefügt.
- (Abschaltbare) Meldung auch bei der Zweierpotenzanpassung der Spaltenanzahl hinzugefügt.
- Kleine Fehlerbereinigungen.
Edit 49: Quelltexte überarbeitet.
Edit 50: Quelltexte nochmals leicht überarbeitet. Kleinen Fehler im beschleunigten Selectionsort behoben.
Edit 51:
- optionale Prüfung und Ausgabe der Stabilität hinzugefügt,
- Stabilität bei einigen Mergesorts implementiert und
- modifiziertes Simpleswapmerge (mit zwei verschiedenen, aus dem SGI-Mergesort entnommen Mergeformen) hinzugefügt.
Edit 52: Jeweils ein Natural- und ein Mergesort „stabilisiert“, und zwar die mit dem Shufflemerge nach John Ellis & Minko Markov. Bubblesort teilweise beschleunigt; es ist jetzt adaptiv, d.h., es sortiert bei (vor-)sortierten Mengen schneller.
Edit 53:
- eine weitere Startmenge hinzugefügt (2 vermischte Teilmengen 3),
- rekursives Quicksort wurde stackoptimiert und
- Proportion Extended Sort hinzugefügt.
Edit 54: Ein weiteres In-Situ-Mergesort hinzugefügt, und zwar eines mit Shufflemerge nach Elif Acar, Mehmet Emin Dalkiliç und Görkem Tokatli.
Edit 55:
- zwei weitere Startmengen (mehrere vermischte Teilfolgen 1 & 2) hinzugefügt,
- andere Bedienlogik bei der Eingabe der Spalten- und Zeilenanzahl (m.E. verbessert, da weniger Eingaben nötig),
- Parametereingabe für (Natural) Mergesort mit Swapsort und Proportion Extend Sort sowie
- kleine Verbesserungen und Fehlerbereinigungen.
Edit 56: Kleinen Fehler in den Lazarusversionen behoben, der darauf beruhte, daß die Wertzuweisung an ein Spinedit nicht das Ereignis "OnChange" auslöst. Außerdem eine englischsprachige Variante dieses Programmes (beruht auf dem Delphi-2-Quelltext) hochgeladen.
Edit 57: Parametereingabe für n- & F-Heapsort hinzugefügt. Kleine Fehlerbereinigung bei der Eingabe der Zeilen- und Spaltenanzahl.
Edit 58:
- Anzeige der Startmenge (mit allen Einstellungen) erfolgt nunmehr sofort ("in Echtzeit") im Hintergrund (damit entfällt die Schaltfläche für die Anzeige der Startmenge),
- feiner einstellbares Verhalten nach Sortierende und -abbruch sowie
- beide Shearsorts sind nunmehr abbrechenbar.
Edit 59: Kleine Verbesserungen bei der Eingabe (Combobox ist jetzt nicht mehr dauerhaft editierbar) und bei der Ausgabe (Extraklick nach Sortierende und -abbruch ist jetzt nur noch relevant, wenn keine Messagebox mehr erscheint).
Edit 60: Parametereingabe für die beiden Shearsorts hinzugefügt.
Edit 61: Nunmehr ist optionales Speichern (beim Programmende) und Laden (beim nächsten Programmstart) aller wichtigen Einstellungen über eine weitere Checkbox möglich. Zudem wurde der Quellcode zur Größenjustierung des Sortierformulares komplett überarbeitet, er müßte nunmehr stabiler und fehlerärmer sein.
Edit 62: Die Parametereingabe für manche Algorithmen ist nunmehr optional.
Edit 63: Die Sortierkinos sind jetzt netzwerktauglich. Werden sie in einem Verzeichnis ausgeführt, für das keine Schreibrechte existieren, so werden die Inidateispeicherungen in das nutzerspezifische Temp-Verzeichnis verlagert (auf das immer Schreibrechte existieren sollten oder müssen). Damit können die Exedateien auch auf schreibgeschützten Servern gelagert und von Workstations aus gestartet und ausgeführt werden. Ansonsten, bei Schreibrechten im selben Verzeichnis, erfolgt die Schreibung der Inidateien in dasselbe Verzeichnis, in dem auch die Exedatei liegt - wie zuvor.
Edit 64: Optionale Sortierzeitmessung hinzugefügt, Ausgabe verbessert (nur noch ein Meldungsfenster nach jeweiligem Sortierende) und mehrere kleine Fehler beseitigt.
Edit 65: Fehlerhaftes Verhalten beseitigt, das nur in Windows 95 & 98 auftritt, beseitigt: Obwohl Deletefile true zurückliefert, wird die probehalber erstellte Datei (um die Schreibrechte zu prüfen) aus unbekanntem Grunde nicht gefunden und folglich nicht gelöscht. Da auch Deletefile auf einer Windows-
API-Funktion beruht, vermute ich einen Windowsfehler.
Edit 66: Zwei neue Startmengen (die mit "Teilmengen" bezeichneten) und die Option, wie diese angeordnet werden, hinzugefügt. Kleine Fehlerkorrekturen.
Edit 67: Zwei neue Vorsortieralgorithmen (Natural Mergesort und Shearsort) hinzugefügt. Mehrere kleine Fehler in bezug auf die Eingabe der Parameter (für mache Sortieralgorithmen) behoben.
Edit 68:
- Sortieralgorithmus "Symmetry Partition Sort" hinzugefügt
- Block(Subarray)-Swap-Algorithmen über Option hinzugefügt (nur für Symmetry Partition)
- weitere Startmengen hinzugefügt
- kleine Verbesserungen und Fehlerkorrekturen
Edit 69: 2 Straigth-Radix-Sorts (LSD und MSD, wobei das erstere das alte ersetzte) und das sog. Stupidsort (der einfachste aller Sortieralgorithmen) hinzugefügt.
Edit 70: Nunmehr sind ALLE Sortieralgorithmen abbrechenbar. Bei Bogosort kann man jetzt den swapbasierten Enumerationsalgorithmus zwischen dem nach Steinhaus-Johnson-Trotter und einem ziemlich neuen nach Oleg Viktorov wählen.
Edit 71: 3 weitere Radixsorts hinzugefügt sowie kleine Fehler beseitigt.
Edit 72: Bremse verbessert (jetzt nicht mehr sleep-, sondern schleifenbasiert).
Edit 73: Splaysort hinzugefügt. Die Idee dazu stammt von
hier und der Pascal-/Delphiquelltext von
dort.
Edit 74: Radixsort MSD bei den Vorsortieralgorithmen hinzugefügt, jetzt gibt es dort 2 Radixsorts, bei denen zwischen LSD und MSD unterschieden wird.
Edit 75: Fehler in Insertionsort 2 & 3 behoben (Abbruch führte nicht zur Rückkehr zum Sortierauswahlformular).
Edit 76: Die (In-)Stabilität jedes Sortieralgorithmus' wird jetzt schon in der Auswahlliste angezeigt, deshalb ist jetzt die Anzeige der (In-)Stabilität nach jedem Sortieren jetzt mehr voreingestellt, aber weiterhin möglich.
Edit 77:
- Modifiziertes Pancakesort, das die Pfannkuchensortierung mit zwei sog. Pfannenwendern simuliert, hinzugefügt. Das Original benutzt nur einen Pfannenwender und verwendet Mengenumkehrungen ("Reverses"), die Modifikation benötigt keine Umkehrungen, dafür aber zusätzlichen Speicher.
- Programm funktioniert jetzt auch mit vertikalen bzw. Hochkantbildschirmen (mehr Zeilen als Spalten) korrekt.
Edit 78: Kleine Codeoptimierungen.
Edit 79:
- Parallelverarbeitendes (Multithreading-)Quicksort implementiert. Dieses läuft schnell ab 2 Prozessoren, ist aber nicht abbrechenbar und nur in den Delphicompilaten stabil.
- Kleine Fehlerbehebungen
Edit 80:
- Paralleles Multithreading-Mergesort hinzugefügt, was wegen der Vielzahl der Threads ebenfalls nicht abbrechenbar ist. Dieser Algorithmus könnte stehenbleiben: Auf einem meiner Windows XP jedenfalls hängt dieser Algorithmus sich insbesondere bei den Delphi-4-Compilaten gern auf, der genaue Grund ist unbekannt, es hat mit den kritischen Abschnitten zu tun, aber der Code ist geprüft. Dann die Delphi-2-Compilate, die deutlich stabiler sind, oder gar die Lazarus-Compilationen (!) verwenden, bei denen das nicht aufzutreten scheint, oder in der Execute-Prozedur die Befehle für die kritischen Abschnitte ändern (ist kommentiert) und erneut kompilieren, dann läuft es aber nicht mehr ganz so parallel.
- Codeoptimierungen und Fehlerbehebungen, so läuft paralleles Quicksort jetzt auch in den Lazarus-Kompilationen.
Edit 81:
- Das einfachste Quicksort zum besseren Vergleich mit seiner Multithreading-Variante hinzugefügt.
- Iteratives Mergesort als Single-Thread-Variante des Multithreading-Mergesorts hinzugefügt. Sieht dem Natural Mergesort ziemlich ähnlich, ist aber keines.
- Fehler in der Prozedur, die die Elemente-/Spaltenanzahl auf 2er-Potenz rundet, behoben.
- Bei der Eingabe des Shearsort-Parameters wird jetzt das eingebbare Maximum direkt angezeigt.
Edit 82:
- Inverses Sortieren (Sortierprozeß, nicht -ergebnis!) bei Bubble-, Insertion- und Selectionsort hinzugefügt.
- Bubblesort ist jetzt noch adaptiver.
- Insertionsort sucht jetzt binär, was i.d.R. schneller abläuft.
- Bei Shellsort wurden 5 Varianten mit verschiedenen Abstandsfolgen hinzugefügt, jetzt sind es insgesamt 6 verschiedene Shellsorts.
Edit 83: In-situ-Blockswapping- bzw. -Arrayrotationsalgorithmus (für Symmetry Partition Sort), der nur aus einer Schleife besteht und sehr schnell ist, hinzugefügt - gefunden in den Diskussionsbeiträgen unter
http://www.geeksforgeeks.org/program...sal-algorithm/
Edit 84: Cycle-Leader-Block-Swapping-Algorithmus (für Symmetry Partition Sort) hinzugefügt. Der Bremsfaktor kann nunnmehr auch zur Sortierlaufzeit verändert werden: '-' verlangsamt, '+' erhöht die Sortiergeschwindigkeit.
Edit 85: Die beiden parallelen bzw. Multithreadsortieralgorithmen (Merge- und Quicksort) sind jetzt abbrechenbar.
Edit 86: Multithreadingsortieralgorithmen überarbeitet. Da das Multithreadingmergesort auf Mehrprozessorcomputern mit Windows XP fehlerhaft läuft und der Grund dafür der zu sein scheint, daß das mit Compilaten Delphi<5 auftritt, sind die Compilate (Exe-Dateien) nunmehr alle mit Delphi 5 erstellt.
Edit 87: Gleichzeitigkeit beim Multithreading-Quicksort verbessert / erhöht. Der entscheidende Hinweis kam von
Daniel in diesem Beitrage. Vielen Dank dafür!
Edit 88: Gleichzeitigkeit beim parallelen bzw. Multithreading-Mergesort erhöht bzw. verbessert. Außerdem bleibt das Programm auf NTx-Windows nicht mehr bei 37 bzw. 38 OnPaint-induzierten Neuzeichnen-Threads stehen (bei Vista sind es 37, bei XP und davor 38 Threads).
Edit 89: Im Gegensatz
zu dieser Behauptung ist Naturalmergesort sehr wohl parallelisierbar - eine Multithreadingversion dafür wurde implementiert.
Edit 90: Kleine Codeoptimierungen in den oet-Prozeduren und bei den Shearsorts.
Edit 91:
- für Shearsort 2 wurde eine Multprozessing-Variante implementiert,
- beim Multithreading-Quicksort ist ab Windows Vista die Simultaneität bzw. Sequentialität feiner einstellbar,
- beim Naturalmergesort und Shearsort 2 (jeweils Multithreadingvariante) kann jetzt eine Maximalanzahl für die Threads eingegeben werden und
- kleine Codeoptimierungen und Korrekturen.
Edit 92: Die 3 Arraydimensionierungsmethoden (statisch, dynamisch zum Programmstart und dynamisch zur Laufzeit) wurden vereinigt. Sie sind jetzt über Compilerschalter am Beginn der
Unit 1 separat erzeugbar.
Edit 93:
- parallele bzw. Multithreading-/-prozessingvariante für Shearsort Nr. 1 und Shellsort hinzugefügt sowie
- mehrere Korrekturen und Detailverbesserungen.
Edit 94: Darstellung der Menge, wenn alle Linien (neu)gezeichnet werden, (vor allem auf modernen Windows) in den beiden Delphi-Versionen beschleunigt; der Dank geht an die Antwortgeber
in dieser Diskussion. Dadurch kann zudem beim Neuzeichnen auf Extrathreads verzichtet werden.
Edit 95:
- paralleles bzw. Multithreading-Mergesort auf der Basis des rekursiven Mergesorts hinzugefügt (während das von Edit 80 das iterative Mergesort als Grundlage hat). Dieser Algorithmus läuft auf Windows XP erst als Delphi-7-Compilat richtig schön (asynchron und nichtsequentiell), deshalb jetzt Delphi-7-Compilat.
- Stabilität (nicht im Sinne des Sortierens) der schleifenbasierten Multithreadingsorts (Naturalmerge-, Shear- und Shellsort) verbessert, leider sind die Algorithmen dadurch deutlich langsamer.
- etlich weitere Detailverbesserungen.
Edit 96:
- Die iterationsbasierten Multithreadingalgorithmen (Naturalmerge-, Shear(1&2)- und Shellsort) wurden überarbeitet, beschleunigt und evtl. auch zuverlässiger gemacht (dennoch "ggf. fragil"). Bei diesen starten die Threads aus dem Main- bzw. VCL-Thread, und das Maximum der Anzahl gleichzeitiger Threads ist über eine Nutzereingabe begrenzbar. Die Threadkommunikation erfolgt ausschließlich über Variablenänderungen und wartende Pollingschleifen.
- Für diese Algorithmen wurden auch je auch eine Variante implementiert, bei der die Sortierthreads aus einem Extrathread heraus gestartet werden, was recht robust ist ("zuverlässig"). Leider ist dabei keine Begrenzung der maximalen Anzahl simultaner Threads mehr möglich. Die Threadkommunikation erfolgt neben den Pollingschleifen auch über Botschaften, trotzdem laufen diese Algorithmen nicht spürbar schneller als erstere.
Edit 97: Die Anzahl simultaner Threads ist nunmehr bei
allen iterationsbasierten Multithreadingsortieralgoritmen begrenzbar.
Edit 98: Bei den beiden Delphi-Versionen läßt sich das Ausgabeverhalten jetzt nicht nur beim Multithreading-Quicksort, sondern auch beim iterativen, vom Mainthread aus gestartetem Naturalmergesort und Shearsort 2 beeinflussen.
Edit 99:
- Für Radixsort (Most Significant Digit) wurden 6 Multithreadingalgorithmen implmentiert: 4 für iteratives und 2 für rekursives Radixsort.
- Das Einschalten der Ausnutzung des gesamten Bildschirmes erfolgt nun über eine Checkbox (vorher Radiogroup). Mit dem "Graumodus" kann die Checkbox zusätzlich anzeigen, ob der Bildschirm nur in einer Richtung maximal ausgenutzt wird.
Edit 100: Wer den weißen Hintergrund nicht mag, kann diesen jetzt über eine Checkbox abwählen, er wird dann schwarz. Bei monochromatischen Startmengen und bei speziellen Sortieralgorithmen werden dann weiße anstatt schwarzer Linien zur Elementedarstellung genutzt.
Edit 101:
- Minsertion- und rlx-Sort hinzugefügt,
- die acht Blockswapping/-Arrayrotationsalgorithmen aus der Radiogroup „Blocktauschalgorithmus“ stehen neben Symmetry Parition Sort nun auch den beiden modifizierten Simpleswapsorts und dem HP-/SGI-Mergesort zur Verfügung und
- kleine Fehlerbehebungen
Edit 102: Domain
Sortierkino und
Sortier-Kino veröffentlicht.
Edit 103:
- Zähler für Vergleiche und Vertauschungen hinzugefügt, kann am Sortierende angezeigt werden,
- als neunter Blockswapping-/Arrayrotationsalgorithmus wurde eine stabile Sortierung (Splitsort) hinzugefügt (auch wenn das Swappingproblem eigentlich kein Sortierproblem ist), damit wird Symmetry Partition Sort beim zweiten Aufruf mit diesem Algorithmus sogar stabil, und
- kleine Fehlerbehebungen
Edit 104:
- Implementation einer Farbmarkierung während des Vergleichens. Da diese nur bei Slow- und Trippelsort gut sichtbar ist, wurde diese auch nur dafür freigeschaltet.
- einige marginale Detailkorrekturen und -verbesserungen
Edit 105:
- Fehler in Proportion Extend und Symmetry Partition Sort behoben, der bei Eingabe des Parameters 256 und 257 zum Programmabsturz führte. Den Ausschlag gab ein Hinweis von Herrn Prof. Jinchao Chen, dem Autor beider Algorithmen
- Geschwindigkeitsangaben in der Combobox geringfügig überarbeitet
Edit 106:
- Für die Auswahl der zu sortierenden Startmengen wurden weitere Startmengen auf der Basis verschiedener Verteilungen (Dreiecks-, Trapez-, Normal- und asymmetrische Verteilung, teilweise auch inversen Verteilungen) hinzugefügt.
- Die halbsortierten Mengen wurden aus der Auswahl der zu sortierenden Startmengen entfernt. Die Halbsortierung steht jetzt - gemeinsam mit der Vorsortierung - allen Startmengen zur Verfügung.
- Startmengen werden nun wegen ihrer Vielzahl statt in einer Radiogroup nunmehr in einer Combobox angeboten. Damit konnte das Bedienformular verkleinert und sein Layout überarbeitet werden.
Edit 107:
- Auch bei den drei letzten Vorsortieralgorithmen (ehemals als „Halbsortierung“ bezeichnet) ist jetzt das Maß der Vorsortierung veränderbar
- kleine Fehlerkorrekturen
Edit 108:
- 7 Mergingalgorithmen hinzugefügt (einer von Krysztof Dudzinki und Andrzej Dydek, einer von Jingchao Chen und fünf von Pok-Son Kim und Arne Kutzner. Da alle mit verschiedengroßen Teilmengen umgehen können, wurde jeder einmal sowohl für Merge- als auch für Naturalmergesort implementiert, sodaß insgesamt vierzehn Sortieralgorithmen hinzugekommen sind.
- Einen weiteren Blocktausch-/Arrayswap-/-rotationsalgorithmuns (Hybridrotation) hinzugefügt. Sowohl dieser als auch die zuvor genannten sieben Mergingalgorithmen entstammen Prof. Dr. Arne Kutzners Benchmarkingtool.
- Die Ausgabemessagebox erscheint jetzt ungefähr an der Stelle, an der zuvor das Bedienformular stand (vorher immer in der Bildschirmmitte).
- kleine Optimierungen
Edit 109:
- Mergealgorithmus nach Frank K. Hwang und Shen Lin, in und ex situ, für Merge- und Naturalmergesort (damit insgesamt vier neue Sortieralgorithmen) implementiert, er stammt aus dem oben genannten Benchmarkingtool.
- Der Mergealgorithmus von 2007 ist jetzt rekursiv und damit „rein“.
- Der Mergealgorithmus von 2006 instabil wurde gemäß seines stabilen Pendants etwas optimiert.
- Der Mergealgorithmus von 2006 stabil überarbeitet.
- einige Fehlerkorrekturen
Edit 110:
- Elementeswapping bei gleichen Indizes ist sinnlos und wird nun abgelehnt,
- alternatives Heapsort, hier im zweiten Beitrage gefunden (der Dank geht an Daniel) und implementiert,
- die 3 Quicksorts heißen jetzt an- und absteigend sowie stackoptimiert, keine Unterscheidung mehr zwischen rekursivem und iterativem Quicksort (wegen des nächsten Punktes),
- die meisten rekursiven Prozeduren in (pseudo-)iterative umstrukturiert, dabei eine eigene heapbasierte dynamische Stack-Objekt-Klasse verwendet, und die maximale Stackgröße moderat verringert (besser für die Multihtreadingsortieralgorithmen),
- dem Shufflemerge der drei türkischen Informatiker Mrs. Elif Acar, Mehmet Dalkiliiç und Görkem Tokatli (ein Eintrag unter Mergesort) stehen nun alle Blockswappingalgorithmen zur Verfügung (wurde vorher nur durch jeweils 3 Rotationen realisiert) und
- Quelltext(e) überarbeitet, einige kleine Fehlerkorrekturen
Edit 111:
- alle noch verbliebenen Rekursionen „entrekursiviert“, d.h., in Iterationen verwandelt, das war Voraussetzung für den nächsten Punkt,
- maximale Stackgröße auf das zulässige Minimum reduziert,
- das Programm müßte nunmehr mit allen Monitoren (auch mit 5K-Displays) im Vollbildmodus arbeiten,
- kleine Überarbeitungen und Fehlerbereinigungen
Edit 112:
- Mergesort hat nun auch eine invers sortierende Variante,
- Layout des Bedienformulares leicht überarbeitet
Edit 113:Stackemulatorklasse leicht überarbeitet und fehlerbereinigt
Edit 114: Der Parameter (Wachstumsfaktor) bei Proportion Extend und Symmetry Partition Sort kann numehr als Real-/Gleitkommazahl und auch kleiner als 2 eingegeben werden.
Edit 115: 13 Mischungsalgorithmen implementiert, um den Gegensatz zum Sortieren zu demonstrieren.
Edit 116:
- Heapsort zur Liste der Vorsortieralgorithmen hinzugefügt.
- Die Anzahl der voneinander verschiedenen Elemente bei einigen Startmengen ist nunmehr einstellbar. Daraufhin wurden einige wenige Startmengen entfernt, weil diese sich nunmehr „konstruieren“ lassen.
Edit 117:
- Die farbliche Markierung der Vergleiche (bei Slow- und Trippelsort) ist nunmehr zur Laufzeit mit Druck auf "V" (Vergleiche, Sortierkino) bzw. "C" (comparisons, sorting cinema) umschaltbar.
- Weitere Rekursionsbeseitigungen und Fehlerbehebungen.
Edit 118:
- Binärmischen, das implizit schon in zwei Startmengen angeboten wird, ist jetzt auch in den Mischungsalgorithmen der Algorithmenliste enthalten.
- Alle binären Mischungs- und Sortieralgorithmen werden jetzt zentral in einem Unterprogramm ausgeführt.
- Kleinere Detailkorrekturen und -verbesserungen
Edit 119:
- Binärmischen ist jetzt eine Option in den Vorsortieralgorithmen (auch wenn es genaugenommen kein Sortieren ist). Damit konnten zwei Einträge in der Menge der Startmengen entfernt werden.
Edit 120:
- Jetzt kann bei allen zufallszahlenbasierten Startmengen die Anzahl unterschiedlicher Elemente eingestellt werden.
- Einige Fehlerkorrekturen
Edit 120: Die Startmenge „Permutation, Quadrat“ ist jetzt auch bei ungeraden Elementeanzahlen ohne Darstellungsmangel.
Edit 121: Die Startmengen lassen sich jetzt über zwei Comboboxen „Werteerzeugung für die Startmenge“ und „Struktur der Startmenge“ übersichtlicher erzeugen - damit ist zudem eine Erhöhung der Anzahl möglicher Startmengen verbunden.
Edit 122:In die Liste „Werteerzeugung für die Startmenge“ wurde der Eintrag „n Werte, kubisch verteilt“ hinzugefügt (das Prinzip gilt auch für alle höheren ungeraden Potenzen). Das Interessante an dieser Verteilung ist, daß die kumulierte Verteilungsfunktion (erkenntlich an der Oberkante sortierten Menge) zwar stetig, aber an einer Stelle (nämlich in der „Mitte“) nicht differenzierbar ist.
Edit 123:
- In die Liste „Werteerzeugung für die Startmenge“ wurde der Eintrag „n Werte, kubisch (Wurzel) verteilt“ hinzugefügt (das Prinzip gilt auch für alle höheren ungeraden Wurzeln, genauer Wurzelexponenten).
- Sortieralgorithmus „Merge-Insertion-Sort“ hinzugefügt.
Edit 124:
- Splaysort überarbeitet, es zeigt jetzt auch die Anzahl der Vergleiche und Verschiebungen an.
- Red-Black-Sort (auf Basis einer Klasse für Rot-Schwarz-Bäume) hinzugefügt. Grundlage war eine Klasse für Rot-Schwarz-Bäume, die ich hier bzw. dort fand.
Edit 125:
- Merge-Insertion-Sort-Variante gemäß dieser Ausarbeitung implementiert.
- Einige Fehlerkorrekturen. Die gewichtigste ist, daß ich erkannte, daß man die Blockswapping-/Arrayrotationsaufgabe nicht ebenbürtig einer Sortieraufgabe übertragen kann - bei den meisten Algorithmen funktioniert das, jedoch nicht immer. Deshalb ist Splitsort aus der Radiogroup zur Auswahl der Arrayrotationsalgorithmen entfernt worden.
Edit 126: Optimierte Variante des inversen Bubblesorts gemäß
diesem Quellcode implementiert.
Edit 127: 2 kleine Fehler korrigiert.
Edit 128: Option (Checkbox) „maximaler Wertebereich“ hinzugefügt.
Edit 129: IniFile-KLasse „TIniFile“ mit „TMemIniFile“ ersetzt (gilt für die beiden Delphi-Programme und dort ab Compilation mit Delphi 4, darunter bleibt TIniFile gültig).
Edit 130:
- Fehlerkorrektur: Die Vergleiche bei Slow- und Trippelsort werden (nach Druck auf „V“ in der deutschen bzw. „C“ in der englischen Version) nunmehr auch bei monochromer Liniendarstellung angezeigt.
- Mehrere kleine, nicht offen sichtbare Fehler korrigiert.
Edit 131:
- Treesort gemäß dieser Implementation hinzugefügt (der Dank geht an das Forumsmitglied Blup).
- Die Anzahl zu sortierender Elemente bei den beiden simultanen Mergesorts ist nun auf 1024 bzw. 2048 begrenzt.
- Mehrere Fehler korrigiert, Quelltext erheblich überarbeitet (Anzahl der Arrays verringert).
Edit 132: Multithreading-Sortieralgorithmen geringfügig überarbeitet
Edit 133:
- Die beiden Multithreading-Mergesorts sind in den beiden Delphi-Compilaten jetzt (wieder) mit beliebigen Elementeanzahlen zu betreiben. Die Korrektur erfolgte, indem die maximale Stackgröße von ihrem Minimum (16384 bzw. 4000h) um 1 erhöht wurde. Beim Lazarus-Compilat funktioniert das beim 32-Bit-Compilat hingegen nicht, die Begrenzung der Elementeanzahlen muß bei diesem daher bestehenbleiben.
- Kleine Fehler korrigiert.
Edit 134: Implementation der inversen Variante des Slowsorts.
Edit 135: 6 weitere Werterzeugungsmethoden für die Startmenge(n) hinzugefügt
Edit 136:
- Paralleles Selection- und Splitsort implementiert
- Checkbox für Vergleichseinfärbungen entfernt
- Die Vergleichseinfärbungen stehen jetzt (bei) jedem Sortieralgorithmus zur Verfügung; die Umschaltung dafür erfolgt weiterhin über den Tastendruck „V“ (bzw. „C“ in der englischsprachigen Version) während des Sortierens.
- kleine Fehlerkorrekturen und Codeoptimierungen
Edit 137: Multithreadingalgorithmen verbessert
Edit 138:
- je eine Bubble- und eine Trippel-Sort-Variante (beide schneller als ihre stabilen Pendants, dafür instabil) hinzugefügt
- 2 simultane Partitsorts implementiert (benötigen je maximal zwei parallele Sortierthreads, sodaß die Eingabe des Parameters für die Maximalanzahl gleichzeitiger Threads nur mit 1 sinnvoll ist, wenn eine Begrenzung erwünscht ist/wird)
- Multithreadingalgorithmen /-klassen überarbeitet (deren interne Anzahl reduziert, die Anzahl der auswählbaren Multithreadingsortieralgorithmen blieb davon unberührt)
- kleine Fehlerkorrekturen und Codeoptimierungen
Edit 139: 5 Multithreading-Sortieralgorithmen (Comb-, Insertion-, Oet- und Shakersort, letzteres aus Main- und mit extra Startthread) implementiert[*]kleine Fehlerkorrekturen
Edit 140:
- Circle- und Cyclesort gemäß dieser Veröffentlichung implementiert
- kleine Fehlerkorrekturen, Quelltext überarbeitet (Anzahl der Unterprogramme reduziert)
Edit 141:
- 5 neue Sortierverfahren (Circlesort invers, zufällig ablaufend und simultan, Splitsort invers und stackoptimiert)
- Circle- und Cyclesort der Liste (Radiogroup) der Vorsortieralgorithmen hinzugefügt
- kleine Fehlerkorrekturen und Optimierungen
Edit 142:
- Bitonicmerge- und -naturalmergesort mit iterativem Verschmelzen / Merging (mit rekursivem war es schon vorhanden) implementiert - es entspricht dem sog. bitonischen Sortiernetz oder Bitonicsort
- kleine Fehlerkorrekturen
Edit 143:
- simultanes Pancakesort implementiert
- Simultanes Quick-, Radix- (MSD rekursiv) und Splitsort überarbeitet und verbessert. Die Interthreadkommunikation ist bei diesen jetzt nicht mehr nur einseitig von den Eltern- zu den Kindsthreads, sondern wie bei den simultanen Mergesorts bidirektional (Duplex).
- je einen Fehler im simultanen und nichtsimultanen iterativem Mergesort korrigiert
Edit 144:
- 10 weitere Varianten des Bitonicmergesorts, davon 4 mit simultanem Verschmelzen, sowie Mergesort mit zufälliger Verschmelzungsreihenfolge implementiert
- Quicksort in die Liste der Vorsortierungen aufgenommen, das Maß der Vorsortierung kann über die Anzahl der Vorsortierschleifen justiert werden. Das ist eigentlich gemogelt, weil Quicksort rekursiv und eben nicht schleifenbasiert ist, mit der iterierten Variante ist es aber doch möglich.
- kleine Fehlerbereinigungen
Edit 145:
- mehrere Sortieralgorithmen (Merge-, Oet-, Partit- und Shakersort) der Liste der Vorsortier-/-mischungsalgorithmen hinzugefügt
- Die Liste der Vorsortier-/-mischungsalgorithmen ist wegen der neuen Einträge nicht mehr in einer Radiogruppe, sondern ab jetzt in einer Combobox enthalten. Damit ist wieder mehr Platz auf dem Bedienformular, dessen Layout etwas umgestaltet wurde.
- mehrere kleine Fehlerbereinigungen
Edit 146:
- Das Bedienformulares erhielt ein neues, übersichtlicheres, besser strukturiertes Layout (nicht in der Lazarus-Version).
- simultanes Bitonicnaturalmergesort implementiert
- alternatives Smoothsort gemäß dieser Vorlage (C++-Quelltext) implementiert
- Nach der Tastenkombination „Alt+F4“, gesendet direkt auf das Sortier-/Mischungsformular, außerdem gesendet über die Taskleiste und nach „Task beenden“ im Taskmanager wird das Programm nunmehr korrekt beendet.
Edit 147:
- 3 weitere (simple) Blocktauschalgorithmen hinzugefügt.
- Die (optionale, wenn Ausgaben erfolgen) Ausgabemessagebox wird jetzt so hinter dem Mauscursor positioniert, daß die Schaltfläche „OK“ unter dem Mauscursor sich befindet.
- Fehlerkorrektur: Das Bedienformular wurde, sofern die Einstellungen automatisch (beim Programmende) gespeichert und (beim Programmstart) geladen werden, nicht an die letzte Stelle positioniert, sondern immer zentriert.
Edit 148:
- Neues Merge- und Naturalmergesort mit einem einfachen (instabilen und langsamen) Verschmelzen hinzugefügt.
- 3 neue Vorsortieralgorithmen (Bubble, Insertion und Selection je invers).
- Die Bubblesort-Variante ist in Wahrheit / Wirklichkeit ein Simplesort und steht jetzt als Simplesort1 in der Algorithmenliste, das ursprüngliche Simplesort1 ist nun Simplesort 1 invers.
- Quelltext überarbeitet, Änderungen an der Algorithmenliste sind nunmehr schneller und fehlerärmer möglich
- Fehlerkorrekturen: Quicksort in Mischprozedur (Vorbereitung der Menge zum Sortieren bzw. Mischen) und instabiles Trippelsort, Fehlerquelle beim Abbrechen des stabilen Mergingalgorithmus von Kim/Kutzner 2006 beseitigt (ggf. Division durch 0), lag an der Implementation, nicht am Algorithmus selbst
Edit 149:
- Die kontextsensitive Hilfe funktioniert jetzt auch beim Lazaruscompilat (halbwegs), dazu war allerdings die Verwendung eines aktuellen Lazarus' erforderlich.
- Multithreadingalgorithmen überarbeitet, müßten jetzt noch stabiler laufen
- Beseitigung weiterer kleiner Fehler und Ungenauigkeiten
Edit 150:
- Smoothsort-Variante von Dr. Hartwig Thomas implementiert, herzlicher Dank für die Hilfe geht an Frühlingsrolle in dieser und jener Diskussion
- Implementation des Smoothsorts von Keith Schwarz geringfügig überarbeitet (Booleanarray wurde durch Integerzahl ersetzt), der Dank geht an Horst_H in jener Diskussion
- 3 Fehler korrigiert: Die Schleifenanzahl beim Binärmischen als Vormischungsalgorithmus ist jetzt auf das sinnvolle Maximum begrenzt, und der Sortier- bzw. Mischungsalgorithmus wird jetzt auch nach dem Start eingelesen, sofern die Optionen gespeichert werden. Weiterhin wird das Formular nun hoffentlich endlich an der Position placiert, an der es sich bei gespeicherten Optionen zuletzt befunden hatte.
Edit 151: Smoothsort von Hartwig Thomas (Klasse und Routinen) geringfügig überarbeitet und optimiert
Edit 152:
- Heapsort-Variante von Dr. Hartwig Thomas implementiert
- Das Smoothsort von Keith Schwarz und das von Hartwig Thomas sind jetzt abbrechenbar.
- Die Ini-Dateien für das optionale Speichern des Startzustandes bzw. der Startoptionen werden, sofern sie nicht „neben“ der Programmdatei abgespeichert werden können (also im selben Verzeichnis), jetzt nicht mehr im Temp-, sondern im Anwendungsdaten-/„AppData“-Verzeichnis des jeweiligen Benutzers gespeichert.
- Mauscursor „Hintergrundaktivität“ während der Verarbeitung (Sortierens bzw. Mischen), das ist in der Standardeinstellung ein Pfeil inklusive Sanduhr
Edit 153:
- Der Mauscursor zur Laufzeit der Verarbeitung (Sortieren bzw. Mischen) ist jetzt zwischen „unsichtbar“ und „hintergrundaktiv“ umgeschaltet werden.
- Sofern der Mauscursor während der Verarbeitung sichtbar ist, wird nun auch bei den simultanen Sortiervorgängen korrekt angezeigt (Standard: Pfeil und Sanduhr).
- Simultanes Shellsort mit eigenem Startthread korrigiert, es blieb zuvor stehen.
Edit 154:
- Smoothsort der Liste der Vorsortieralgorithmen hinzugefügt.
- 3 weitere Bitonicmergesorts implementiert (stehen am Ende der Bitonicmergesorts: iterativ einfach sowie iterativ und rekursiv simultan).
Edit 155:
- In die Liste der Vorsortierungsalgorithmen wurden Merge- und Quicksort je invers und zufällig sowie zwei weitere Mischungsalgorithmen (Fisher-Yates 1.2 und 2.2) aufgenommen.
- Mit einer weiteren Option (Checkbox) kann nun eingestellt werden, daß die Elemente nur dann getauscht werden, wenn sie ungleich (groß) sind.
- Quelltext überarbeitet: Die Algorithmen, die von der Vorsortierung und von der eigentlichen Sortierung benutzt werden, in gemeinsame(n) Unterprogramme(n) vereint.
- Fehlerbeseitigung: Auch die zufallsbasierten Startmengen können jetzt wieder alle Strukturen der Startmenge bilden.
Edit 156:
- Das iterative und das rekursive simultane Bitonicmergesort haben jetzt - neben dem einfachen bitonischen Verschmelzen, das sie als Verschmelzungsverfahren schon hatten - jetzt je auch ein iteratives simultanes bitonisches und ein rekursives simultanes bitonischesVerschmelzen bekommen (Simultaneität auf zwei Ebenen).
- Das Merge- und das Naturalmergesort mit dem stabilen Verschmelzen von Ellis und Markov haben jetzt je auch eine instabile Versions des Verschmelzens der genannten Autoren.
- Nicht nur die Position des Bedienformulares, wie es schon lang möglich ist, sondern nunmehr auch die Position des Prozeßformulares (das, auf dem das Sortieren bzw. Mischen stattfinden) wird jetzt vom optionalen Speichern und Laden erfaßt, sofern das Prozeßformular einen umgrenzten bzw. Fenstermodus hat und mithin verschiebbar ist.
Edit 157:
- Zähler für die Threads und optionales Anzeigenlassen dieses Wertes nach Sortierende implementiert.
- Fehler, daß manche simultanen Bitonicmergesorts nicht starteten, korrigiert.
Edit 158: In-Situ-Variante des Splitsorts implementiert.
Edit 159:
- Stabiles Quicksort gemäß diesem bzw. jenem Projekt implementiert.
- IDie Startparameter (für manche Sortieralgorithmen relevant) werden nun in die optionale Speicherung und Ladung der Einstellungen einbezogen.
- Kleine Fehler beseitigt.
Edit 160:
- Zwei weitere stabile Quicksorts gemäß diesem bzw. jenem Projekt implementiert.
- wenige geringfügige Detailverbesserungen
Edit 161: Stabiles Heapsort und eine weitere Smoothsort-Variante gemäß
diesem bzw.
jenem Projekt implementiert.
Edit 162:
- Bei den Vertauschungen wird jetzt nicht mehr der Verschiebungszähler um drei (Vertauschungen bestehen aus drei Verschiebungen), sondern ein eigens eingeführter Vertauschungszähler um ein erhöht.
- Bubble- und Insertionssort vorwärts und invers liegen jetzt in je einer Variante auf der Basis von Verschiebungen und je einer Variante auf der Basis von Vertauschungen vor.
Edit 163:
- Fehler beseitigt, die meistens auftraten, wenn bei den letzten beiden stabilen Quicksorts die Puffergrößen größer als 0 eingegeben wurden.
- Die aus dem originalen Quelltext übernommene Stackersatzstruktur (Array) für die drei stabilen Quicksorts durch die „hauseigene“ Stackemulatorklasse ersetzt.
Edit 164:
- Grail-, Tim- und Naturalmergesort (das wie einfaches Mergesort aussieht) implementiert. Die beiden erstgenannten wurden aus diesem bzw. jenem Projekt extrahiert.
- Fehler beseitigt: Beim häufigen Klicken auf das Prozeßformular vor dem Sortieren bzw. Mischen wurden die etliche Startmengenstrukturen manchmal nicht korrekt dargestellt.
Edit 165:
- Grailsort in eine originale Variante mit dem Grailmerge und eine mit dem einfachen Verschmelzen aufgespaltet.
- Merge- und Naturalmergesort je einmal mit dem Grailmerge hinzugefügt.
- Sqrt-Sort aus dem Projekt wie im Eintrag zuvor implementiert.
- Rekursives Grailmerge aus demselben Projekt für Grail-, Merge- und Naturalmergesort implementiert.
Edit 166:
- Fehlerkorrektur: Grailmerge „stabilisiert“.
- Kontextsensitive Hilfe für die Radiogruppe zur Auswahl des Blocktauschalgorithmus' hinzugefügt.
Edit 167: Mergesort mit In-Situ-Verschmelzen aus dem zuvor genannten Projekt extrahiert und in dieses Projekt implementiert.
Edit 168:
Edit 169:
- Shufflemerge von John Ellis und Minko Markow von rekursiver in iterative Form umgewandelt, dafür eine weitere, flexiblere Stackemulatorklasse (auf der Bais von Zeigern / Pointern) implementiert
- beide Stackemulatorklassen (die, die nur mit dem Datentyp „word“ arbeitet und die neuere auf der Basis von Zeigern) in eine Extraunit ausgelagert
- das zweite Shufflemerge (das der drei türkischen Informatiker) leicht vereinfacht
Edit 170: Fehler beseitigt, der auftrat, wenn bei den Zufallszahlen die Anzahl n verschiedener Elemente auf 1 gesetzt und danach für die Werteerzeugung die natürlichen Zahlen (je einmal) gewählt wurde(n).
Edit 171:
- Korrektur: Das perfekte Außen- und Innenmischen waren vertauscht.
- Vier weitere Einträge auf Basis des perfekten Mischens der Liste der Sortier- und Mischungs- sowie der Vorsortier- und -mischungsalgorithmen hinzugefügt.
Edit 172:Ein Merge- und ein Naturalmergesort jeweils mit einem neuen Mergingalgorithmus nach Prof. John Ellis und Prof. Ulrike Stege gemäß
dieser Anleitung implementiert. Laut Beschreibung ist er stabil, jedoch konnte die Stabilität in dieser Implementation nicht erreicht werden, Grund unbekannt. Wird sobald wie möglich verbessert.
Edit 173:
- Merge- und Naturalmergesort mit Duelmerge implementiert. Dieser Mergealgorithmus stammt von Prof. Dr. Sergio Luis Sardi Mergen und Prof. Dr. Viviane Pereira Moreira.
- Den neuen Mergealgorithmus von Prof. John Ellis und Prof. Ulrike Stege geringfügig korrigiert und ergänzt, ist aber leider immer noch instabil.
- Die Bremse während der Verarbeitung wird nun mit Druck auf „-“ halbiert (vorher um 1 vermindert) und auf „+“ verdoppelt (vorher um 1 erhöht), zudem ist der Maximalwert der Bremse jetzt 9999, und auch bei großer Bremse kann nunmehr die Verarbeitung unverzüglich abgebrochen werden.
Edit 175: Den neuen Mergealgorithmus von Prof. John Ellis und Prof. Ulrike Stege erneut überarbeitet (2 weitere Fehler korrigiert und ihn zudem „stabilisiert“, d.h., stabil gemacht).
Edit 176: Quelltext überarbeitet, den Code (auch den ausführungsrelevanten) dabei etwas komprimiert.
Edit 177: Patiencesort in situ (2 Varianten) und ex situ implementiert.
Edit 178:
- 5 weitere Quicksortderivate hinzugefügt (alle bei den Quicksorts zu finden): 3-Wege-Quicksort, Meansort, IQ-, O- und GO-Sort (alle entnommen der Ausarbeitung zu Sortieralgorithmen „Sorting - The Turku Lectures“ (auch zu finden als TUCSLectureNotes22.pdf))
- Korrektur mehrerer kleiner Fehler
Edit 179: 4 weitere Sortieralgorithmen hinzugefügt:
- Heapsortvariante von Robert W. Floyd und inverses Heapsort gemäß diesen Vorlesungsfolien; das inverse Heapsort wurde zudem auch noch in die Vorsortierungsalgorithmenliste eingefügt
- halbstabiles Quicksort (nur die linke Partition ist stabil) gemäß diesem Quelltext
- stabiles Quicksort nach Thomas Müller, diesem Java-Projekt entnommen
Edit 180:
Edit 181:
- Merge- und Naturalmergesort mit rekursivem Verschmelzen gemäß dieser Ausarbeitung von Franco P. Preparata implementiert
- Mergesort mit iterativem Verschmelzen von Franco P. Preparata (aus demselben Skript) implementiert
- bei den Blockswapping-/Arrayrotationsalgorithmen einen Rechtsverschiebealgorithmus (Rightshift, aus demselben Skript) von Franco P. Preparata hinzugefügt
- Die Initialisierung des Zufallszahlengenerators beim Programmstart ist jetzt optional (aber immer noch voreingestellt).
- mehrere Fehler beseitigt
Edit 182:
- Das Mergesort mit dem Verschmelzen von Elif Acar & Co. sowie das mit dem iterativen Verschmelzen von F. Preparata funktionieren jetzt mit allen Elementeanzahlen (falls die zu verschmelzenden Teilarrays ungleich sind, wird einfaches Verschmelzen verwendet).
- mehrere Fehler beseitigt
Edit 183: Blockmerge sowie stabiles und instabiles Partitionsmerge nach
Luis Isidoro Trabb Pardo gemäß seiner Anleitung "
Stable sorting and merging with optimal space and time bounds" implementiert.
Edit 184:
- das zuvor implementierte Partitionsmerge „stabilisiert“
- Parametereingabe für diesen Mergingalgorithmus hinzugefügt
Edit 185:
- Shufflemerge von Elif Acar & Co. „stabilisiert“
- instabiles Shufflemerge von John Ellis und Minko Markow entfernt (stabile Variante bleibt)
- Eine zusätzliche „Stabilisierung“ kann jetzt bei ausgewählten instabilen Sortieralgorithmen während des Sortierens oder generell nach dem Ende einer jeden Sortierung zugeschaltet werden.
Edit 186: Die globale Stabilisierung nach dem Sortieren wurde beschleunigt; sie funktioniert jetzt außerdem auch nach den simultanen Sortieralgorithmen
Edit 187:
- weiteres bedingt stabiles Heapsort von Hartwig Thomas sowie ein Merge- und ein Naturalmergesort mit Mergealgorithmus von Vaughan Donald Pratt implementiert
- Rekursion beim Mergealgorithmus von Jingchao Chen und beim Mergesort von Andrej Astrelin und Christopher Swenson entfernt
Edit 188: Stabiles Quicksort mit einem stabilen Partitionsalgorithmus und einen weiteren Blockswappingalgorithmus, beide nach Ronald Linn Rivest, implementiert
Edit 189: Die Option, mit der einzugebende Parameter hinzu- oder abgeschaltet werden können, ist nunmehr nur noch bei den dafür relevanten Sortieralgorithmen freigeschaltet.
Edit 190: 4 neue Sortieralgorithmen hinzugefügt:
Edit 191:
- Merge- und Naturalmergesort mit Verschmelzungsalgorithmus nach Heikki Mannila und Esko Ukkonen hinzugefügt
- VRF(V-RE-FR-)Sort von vier indischen Informatikern implementiert
Edit 192: Drei Verschmelzungsalgorithmen hinzugefügt:
- Vereinfachter Algorithmus nach Heikki Mannila und Esko Ukkonen, der nicht blockweise, sondern kontinuierlich verschmilzt
- rekursives Verschmelzen nach Viktor J. Duwanenko
- Verschmelzen nach Kanagavelu Sugumar; da dieses Verschmelzen nicht für die Fälle geeignet ist, in denen das rechte Teilarray größer als das linke ist, ist es für Naturalmergesort ungeeignet und wird deshalb nur beim Mergesort angeboten, sowie
- zwei einfache, schnelle In-Situ-Blocktauschalgorithmen (einer auf Basis von Verschiebungen, der andere auf der Basis von Vertauschungen) implementiert
Edit 193: Drei Mergesorts mit asymmetrischer Partitionierung hinzugefügt, zwei davon erlauben eine Eingabe zur Variation des Größenverhältnisses der Teilarrays.
Edit 194:
- Ein weiteres asymmetrisches Mergesort mit konstantem Teilungsverhältnis, aber zufälliger Anordnung der längeren und kürzeren Teilarrays, hinzugefügt.
- Zwei bidirektionale Insertionsorts implementiert.
- Bidirektionales Insertionsort der Liste der Vorsortierungsalgorithmen hinzugefügt.
Edit 195:
- Sind beim Blöcketausch(en) die Blöcke gleich groß, können sie nunmehr optional unabhängig vom gewählten Blocktauschalgorithmus immer schnell getauscht werden.
- Weitere Option: Bei Verschiebeoperationen kann jetzt - wie es eigentlich korrekt ist - das Startelement nach dem Verschieben eingenullt und dieses auch angezeigt werden
Edit 196: 6
weitere Mergingalgorithmen nach Jyrki Katajainen & Co. hinzugefügt:
- Originalalgorithmus
- wie Original, jedoch inverser Sortierverlauf, aber gleiches Sortierergebnis
- Variante, die mit nur einem Mergingalgorithmus auskommt
- inverse Variante der Variante zuvor
- stabilisierbare Variante der Originalversion
- inverse stabilisierbare Variante der Originalversion
Edit 197: Die Möglichkeit, mit jedem Mausklick auf das Verarbeitungsformular eine neue Startmenge zu erstellen, kann jetzt mit einer weiteren Checkbox abgeschaltet werden.
Edit 198:
- Zwei Mergesorts und ein Naturalmergesort mit dem erweiterten Mergealgorithmus nach Jyrki Katajainen & Co. (Quelle siehe Edit 196) implementiert.
- Etliche kleine, subtile Fehler beseitigt.
Edit 199:
- Ein Merge- und ein Naturalmergesort mit dem Deompositionsmerge nach Bransilav Durian und S. Dvorák implementiert
- Nicht nur die Verschiebungen, sondern auch die Vertauschungen können jetzt korrekt dargestellt werden (zusammengefaßt unter „richtiges Bewegen“).
- Etliche Detailkorrekturen.
Edit 200: Nur interne Änderungen ohne Einfluß auf Bedienung und / oder Animation:
- beim Kompositionsmerge den Stack ähnlich der Beschreibung (s.o.) entfernt
- Rekursionen beseitigt (Unterprogramme: BuildSubHeap, BuildCraigsSubHeap, PushDown, PushDownLeftFirst, StableBinaryPivotTP (alle von Craig Brown))
- Prozeduren BuildSubHeap und BuildCraigsSubHeap wegen großer Ähnlichkeit zur Prozedur Build_Craigs_SubHeap_2_in_1 vereinheitlicht / zusammengefaßt
Edit 201:
- Die „Anzahl n verschiedener Elemente“ ist jetzt mit Klick auf eine weitere Checkbox schnell und einfach wieder (re-)maximierbar
- Algorithmus hinter dem siebenten Eintrag der Combobox „Struktur der Startmenge“ korrigiert
Edit 202:
- Das Shufflemerge von Elif Acar & Co. ist jetzt auch bei den Naturalmergesorts vorhanden. Grundlage ist eine Prozedur, die das Verschmelzen immer gleichgroßer Teilbereiche gewährleistet.
- Das erweiterte Scratchmerge nach Jyrki Katajanen & Co. ist nunmehr in zwei Varianten bei den Naturalmergesorts vertreten.
- Wenige kleine Fehler bereinigt.
Edit 203:
- Ein zweites Naturalmergesort, das wie ein einfaches Mergesort aussieht, implementiert. Das neue hat aber im Gegensatz um ersten genau die gleichen Verschmelzungen wie einfaches Naturalmergesort.
- Das iterative Verschmelzen von Franco P. Preparata und das Verschmelzen von Kanagavelu Sugumar sind jetzt auch bei den Naturalmergesorts verfügbar.
- Erinnerungsfunktion für die Position des Verarbeitungsformulares im Fenstermodus, wenn das zwischenzeitlich im fensterlosen Modus, also z.B. im Vollbildmodus geschaltet war
- Bei der Eingabe der Fließkommazahl für den Wachstumsfaktor beim Proportion Extend und Symmetry Partition Sort kann jetzt, egal, ob die deutsch- oder englischsprachige Version, beliebig ein Punkt oder Komma verwandt werden.
- Werteausgabe etwas vereinfacht. Bei der Angabe der (In-)Stabilität wird nunmehr auch die Anzahl der Stabilitätsinversionen ausgegeben.
- Stackemulations-Unit etwas überarbeitet
- Etliche kleine Fehler, vor allem deklarierte, aber überflüssige (nicht verwendete) Variablen bezeitigt. Der größte war, daß das Bedienformular nach der Verarbeitung nicht wieder erschien, wenn es keine Ausgaben gibt.
Edit 203: Mergealgorithmus von Heikki Mannila und Esko Ukkonen, zu finden je einmal bei den Merge- und den Naturalmergesorts, überarbeitet. Er ist jetzt (pseudo)rekursiv.
Edit 204: Positionierung der Werteausgabemitteilungsfensters überarbeitet (in den beiden mit Delphi compilierten Versionen).
Edit 205: Rekursives Naturalmergesort hinzugefügt (inspiriert von
http://cs.uno.edu/people/faculty/bil...-Regl-1993.pdf).
Edit 206:
- Option „Rotation“ hinzugefügt, damit kann die Startmenge nach links oder rechts verschoben werden. Dafür zwei Punkte in „Struktur der Startmenge“ entfernt („kleinstes Element hinten“ und „größtes Element vorn“), weil beides mit der neuen Option auch erzeugbar ist.
- Mergesort nach „The Pairwise Sorting Network“ nach Prof. Dr. Ian Parberry implementiert
- Die Verarbeitung (Sortieren oder Mischen) kann jetzt auch mit Entertastendruck (wenn ein entsprechender Algorithmus ausgewählt wurde) gestartet, das Programm im Auswahlmodus (wenn das Bedienformular erscheint) mit ESC-Tastendruck beendet werden.
- mehrere kleine Detailkorrekturen und -verbesserungen
Edit 207:
Annealing- und Spin-the-bottom-Sort (auch
hier) von
Prof. Dr. (PhD) Michael T. Goodrich sowie zwei Quicksorts mit perfekter bzw. fast perfekter Halbierung bei der Partitionierung implementiert.
Edit 208: Bitonisches Merge- und Naturalmergesort je
mit rekursiver Verschmelzungsprozedur für beliebige Elementeanzahlen und mithin auch für unterschiedlich große Teilarrays implementiert (iterative Verschmelzungsprozedur auch für verschieden große Teilarrays und damit für (Natural-)Mergesort für beliebige Elementeanzahlen war schon implementiert).
Edit 209:
Randomisiertes Shellsort (auch
hier) nach Michael T. Goodrich hinzugefügt.
Edit 210: 3 vereinfachte und modifizierte Versionen des
Zig-Zag-Sorts (auch
hier) nach Michael T. Goodrich implementiert.
Edit 211: Fünf Versionen des
Fun-Sortes implementiert
Edit 212: Jeder Verarbeitungsalgorithmus (Sortieren bzw. Mischen) kann mit Druck auf „P“ oder „p“ prozessorschonend unterbrochen (pausiert) und mit gleichenm Drucke auch wieder fortgesetzt werden.
Edit 213: 4 weitere Startmengenstrukturen (je zweimal zwei verschiedengroße sortierte Teilmengen und mehrere verschiedengroße sortierte Teilmengen) implementiert
Edit 214:
- Bei den Quicksorts als Vorsortieralgorithmen kann (neben der schon vorhandenen Schleifenanzahl) nunmehr auch die Rekursionstiefe eingestellt werden.
- Bei jeder Veränderung des Vorsortier-/mischungsalgorithmus' wird die Anzahl der Vorsortierschleifen wieder auf 1 zurückgestellt, weil manche dieser Algorithmen bei schon eingestellten großen Schleifenanzahlen „hängen“ (und nicht abgebrochen werden) können.
Edit 215: Vom beschleunigten Naturalmergesort, das abfallende Teilmengen erkennt und invertiert, eine instabile Version implementiert.
Edit 216: Ein weiteres Bead-/Gravitysort hinzugefügt.
Edit 217:
- Bei den beiden Timsorts kann jeweils der Parameter „MinRun“ vor dem Sortieren geändert werden.
- Weitere Startmengenstruktur („teilweise sortiert“) hinzgefügt. Die Anzahl der Tauschpaare kann dabei eingestellt werden.
- zwei grobe Fehler (einer machte viele Startmengenstrukturen zunichte, der andere verhinderte die Stabilitätsanzeige zum Sortierende) entfernt.
Edit 218:
- Die Tauschpaare, in der vorherigen Programmversion noch als neue Startmengenstruktur eingeführt, ist nunmehr in die Liste der Vorsortierungs- und -mischungsalgorithmen verlagert.
- Optimiertes Stupidsort implementiert. Das Alleinstellungsmerkmal der einzigen Schleife des Stupidsorts geht bei dieser Optimierung allerdings verloren.
Edit 219:
- Merge- und Naturalmergesort mit Weavemerge aus w0rthys Projekt implementiert.
- Mehrere subtile Fehler entfernt.
Edit 220:
- Ineffizientes Selectionsort („Badsort“) implementiert.
- Bozosort 1 und 2 zu einem Bozosort (Bozosort 1) zusammengefaßt, die Numerierung der verbleibenden drei Bozosorts entsprechend angepaßt.
- Zufallsmischen 1.1 und 1.2 zu einem Zufallsmischen (Zufallsmischen 1) zusammengefaßt.
- Bozosort 1 und Zufallsmischen 1 beruhen nun auf einem gemeinsamen Unterprogramm. Bei beiden kann die maximale Tauschdistanz eingestellt werden.
Edit 221:
- Merge- und Naturalmergesort mit einem einfachen Verschmelzen aus w0rthys Projekt implementiert.
- Sillysort von derselben Quelle in zwei Versionen hinzugefügt.
- Ebenfalls zwei Versionen, bei denen Silly- und Slowsort kombiniert werden, implementiert.
Edit 222: Iteratives Odd-Even-Mergesort, iteratives Pairwise Sorting Network und
Dual-Pivot-Quicksort, alle gefunden
in diesem Javaprojekt von Piotr Grochowski, hinzugefügt.
Edit 223: Einige Startmengenstrukturen können jetzt mit unterschiedlicher Qualität erstellt werden (die exakten Methoden sind die bisher schon implementierten).
Edit 224: 14 weitere Shellsorts mit je verschiedenen Distanzfolgen hinzugefügt.
Edit 225:
- Das optimierte Bubblesort gibt es nun auch in einer Vorwärtsvariante.
- Merge- und Naturalmergesort mit 4-Band-Verschmelzen implementiert. Ersteres funktionier aber nur, wenn die Elementeanzahl eine Zweierpotenz ist.
Edit 226: Binary Search Tree Sort auf der Grundlage
des Quelltextes von Roman Tereshin alias ramntry implementiert.
Edit 227: 3 Sortieralgorithmen implementiert:
Edit 228: Den Blocktauschalgorithmus aus dem Rotatequicksort der Liste (Radiogroup) der Blockswappingalgorithmen hinzugefügt.
Edit 229:
- Zwei weitere iterative Quicksorts hinzugefügt. Das Grundgerüst dazu fand ich auf Github. Das Select-Unterprogramm beider unterscheidet sich: Einmal gemäß Median of Medians, das andere Mal Quickselect.
- Kontextsensitive Hilfe bei der oberen Auswahlbox („Werteerzeugung für die Startmenge“) hinzugefügt.
Edit 230:
- Simpleswapmerge in einer weiteren, diesmal stabilen Modifikation für Merge- und Naturalmergesort implementiert.
- Das vereinfachte Verschmelzen nach Heikki Mannila und Esko Ukkonen gab es bisher nur in einer Vorwärtsversion. Eine Rückwärtsversion und eine mit abwechselndem Verschmelzen (verschmilzt von außen nach innen) wurde hinzugefügt und ebenfalls für Merge- und Naturalmergesort bereitgestellt.
Edit 231:
- Blocktauschalgorithmus „Kreuzindex“ in drei Geschwindigkeitsstufen implementiert (nur in situ).
- Das vereinfachte Verschmelzen nach Heikki Mannila und Esko Ukkonen in der Bidirektionalvariante für Merge- und Naturalmergesort auch in einer beschleunigten Version implementiert. Es nutzt eine Abwandlung der zuvor genannten schnellen Kreuzindizierung.
Edit 232:
- IM-Sort nach Larry Liu Xinyu (auch hier) implementiert.
- Drei Blockstauschalgorithmen der Standard Template Library nach einem Skript von Ching-Kuang Shene sowie eine Eigenvariante der Variante 1 (dann mit der Nummer 4) hinzugefügt. Die Blocktauschalgorithmenauswahl erfolgt jetzt nicht mehr über eine RadioGroup, sondern über eine ComboBox.
Edit 233: Das Fisher-Yates-Mischen gibt es jetzt auch in der Vorwärtsvariante (die bisherige arbeitete rückwärts) und sowohl die Vorwärts- als auch die Rückwärtsvariante nunmehr in zwei Versionen.
Edit 234:
Healysort,
Merge2Sort und
Shovesort (letzteres vorwärts und rückwärts) hinzugefügt.
Edit 235: Beim Swirlsort eine Vorwärtsvariante implementiert (die bisherige funktioniert rückwärts).
Edit 236:
Edit 237:
- QuickMergesort nach Stefan Edelkamp und Armin Weiß hinzugefügt. Die beiden Quellen dazu lauten "QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting" und "Worst-Case Efficient Sorting with QuickMergesort" und sind leicht als PDF-Dateien im Internet zu finden.
- Beschleunigtes Quickmergesort mit einem modifizierten Scratchmerge (Original von Alexander Kronrod) implementiert.
Edit 238:
- Die beiden Quickmergesorts, die in der vorherigen Version implementiert wurden, waren ein wenig vereinfacht. Deshalb wurden zwei weitere, komplexere Quickmergesorts (ebenfalls nichtbeschleunigt und beschleunigt), die näher an der Beschreibung und den Ideen der Autoren sind, implementiert.
- Merge- und Naturalmergesort je mit enhanced in-place merge nach Vignesh R. und Tribikram Pradhan implementiert.
Edit 239:
- Das Bose-Nelson-Sorting-Network, in diesem Projekt gefunden, implementiert (Dank an Armin Weiß).
- Bei den Strukturen der Startmenge fünf (selbstähnliche) Fraktale hinzugefügt. Ihre Feinheit ist über die maximale Rekursionstiefe einstellbar.
Edit 240:
- Blockquicksort je mit einfachen Vertauschungen und mit zyklischen Verschiebungen nach Stefan Edelkamp und Armin Weiß hinzugefügt (Quelle unter Edeit 239).
- Den Bereich mit den Fraktalen bei den Startmengenstrukturen (die letzten Einträge) überarbeitet und erweitert.
Edit 241: Blockquicksort mit Finish-Partitionierung nach Stefan Edelkamp und Armin Weiß (Quelle unter Edit 239) sowie ein weiteres iteratives Quicksort implementiert.
Edit 242:
Friendssort nach Sardar Zafar Iqbal, Hina Gull und Abdul Wahab Muzaffar sowie beschleunigtes Friendssort implementiert.
Edit 243: Merge- und Naturalmergesort mit Wandermerge (eigenentwickelter, bedingt stabiler In-Situ-Verschmelzungsalgorithmus) implementiert. Findet sich jeweils direkt unter den Einträgen des Merge- bzw. Naturalmergesorts mit dem Verschmelzungsalgorithmus nach Vaughan Donald Pratt.
Edit 244:
Q-Sort (auch
dort) von
Jon Louis Bentley implementiert.
Edit 245: Nur für die beiden Delphi-Versionen:
- Das Verarbeitungsformular kann außer bei der letzten Werteerzeugungsmethode nunmehr „manuell“ mit der Maus in seiner Größe verändert werden.
- Die Option „Zoom“ neben der Spaltenanzahlseinstellung erlaubt nunmehr breitere Spalten - Balken statt Linien. Dafür wird der Bresenham-Algorithmus benutzt (siehe hier mit Dank an Flogo).
Antwort
21. Okt 2009, 06:53
, aber den Code solltest Du so nicht freigeben. Versuche mal, das Ganze mit OOP umzusetzen.
Zitat
Zitat von alzaimar:
Linear-Darstellung
