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:

1. 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.
   
   
2. Von der Laufzeit her schon um Größenordnungen besser, aber immer noch grottenschlecht sind bestimmte rekursive Algorithmen: Slow- und Trippelsort.
   
   
3. 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.
   
   
4. Verbesserte, d.h. asymptotisch gute Algorithmen wie z.B. Shell-, Gap- und Shearsort.
   
   
5. 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. .
   
   
6. 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: home.arcor.de/peter-...l/sortieralgorithmen (die schaltete er dankenswerterweise privat wieder frei, nachdem die von ihm vor einigen Jahren abgegebene 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

Edits bitte unter www.delphipraxis.net...tieralgorithmen.html nachlesen, weil die hiesige Forensoftware sonst mit der Größe dieses Beitrages nicht klarkäme.

Und jetzt die Zugabe - die Farbvariante der drei o.a. Programme!

Damit schleppt jeder Wert im Verlaufe der Sortierung anhand seiner Farbe seine (ungefähre) Startposition mit sich umher.

Auf diese Weise ist es möglich, die (In-)Stabilität mancher Sortieralgorithmen optisch wahrzunehmen. Dazu empfehle ich die letzte Startmenge - die mit zwei konstanten Teilmengen, abfallend.

Achtung: Diese Farbzuordnung funktioniert nicht bei den speziellen Sortieralgorithmen (Bucketsorts): Beatsort, Distribution Counting und Straight Radix Sort, d.h. konkret, die Farbzuordnung bleibt im Verlaufe der Sortierung nicht erhalten/enthalten. Die Endfärbung der sortierten Menge ist gleich kontinuierlich wie die Startfärbung.

Vielleicht meldet sich ja diesmal ein glücklicher Finder irgendeines (oder mehr als eines) Fehlers.

Viel Spaß erneut oder weiterhin!

Delphi-Laie

Edit: Beide Quicksorts beschleunigt: Tausch nur noch nach Schlüsselvergleich. Damit vermischen beide Algorithmen die Elemente gleichgroßer Schlüssel auch nicht mehr unkontrolliert, sondern werden wenigstens „invers stabil“ (=bei Elementen gleichgroßer Schlüssel wird deren Reihenfolge invertiert).

Edit 2: 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 3: Swirlsort korrigiert (Farbinformation blieb im Verlaufe der Sortierung nicht erhalten).

Edit 4: 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 5: 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 6: Subtilen Fehler bei der Generierung der Startmenge „2 separate absteigende Teilmengen“ korrigiert. Dynamische Längenanpassung der (zu sortierenden) (Haupt-)Menge korrigiert.

Edit 7: Anhänge gelöscht, weil beide Programmversionen verein(ig)t wurden - siehe vorherigen Beitrag.

Hallo,

das sieht ja mächtig bunt aus und manchmal ist es auch stabil.
Vielleicht habe ich es übersehen, aber wäre ein Zähler für Vergleiche und Vertauschungen machbar?
Vielleicht in einer Unterabteilung als Vergleich verschiedener "vernünftiger" Sortierverfahren.
Wenn Du es richtig eilig hast, könnte das Zeichnen horizontaler, statt vertikaler, Linien schneller sein.

Gruß Horst

Danke!

Horst_H hat folgendes geschrieben :

das sieht ja mächtig bunt aus

Mächtig bunt? Mächtig bunt sind die Haribobtüten aus Redmond.

Ich verwandte von den Basisfarben die beiden dunkleren mit zwei gegenläufigen Gradienten, um die (ungefähre) Startposition zu erhalten. Das ist nicht mehr bunt als nötig! Für „mächtig bunt“ fehlt die dritte Grundfarbe! Ansonsten die Schwarz-Weiß-Variante, die diese Informationen aber nicht bieten kann (und man damit die (In-)Stabilität nicht verfolgen läßt).

Horst_H hat folgendes geschrieben :

und manchmal ist es auch stabil.

Manchmal? Wann und wann nicht? In welcher Weise „nicht stabil“? Das ist mir für eine Fehlerbeschreibung viel zu unsubstantiiert.

Falls Du die Störungen im Bildschirmaufbau meinst, dazu schrieb ich am andern Ort:

„Vermutlich ein von Windows verursachten Neuzeichnen. Habe mich damit wirklich lang beschäftigt. Also, ein solches Ereignis sollte die bis dato temporär sortierte Menge (von mir programmiert) neuzeichnen lassen, so meine Idee. Dazu hätte das Sortieren unterbrochen werden müssen. Ein extra Thread drängte sich geradezu auf (meine erste Begegnung mit Threadprogrammierung). Nur, zwei Threads, die auf ein Formular zugreifen, benötigen Synchronize (sonst Abstürze oder anderes unkontrollierbares Verhalten). Der Sortierthread ist jedoch voll ausgelastet, und Synchronize lähmt damit auch den anderen, eigentlich das Ereignis überwachenden (und ggf. die Sortiermenge neuzeichnenden) Thread. Pustekuchen, damit war ich mit meinem Latein am Ende. Sonst hatte ich bis Delphi immer meine Wünsche erfüllt bekommen, doch das war das erste Mal, daß ich an dessen Grenzen geriet (oder kennt jemand eine Lösung?). So blieb es beim Neuzeichnen der Sortiermenge nach Ende des Sortierens.“

Horst_H hat folgendes geschrieben :

Vielleicht habe ich es übersehen, aber wäre ein Zähler für Vergleiche und Vertauschungen machbar?

Bläht den Quelltext deutlich auf, für das Laufzeitverhalten allerdings eher irrelevant. Einen Schleifenzähler fügte ich nur den beiden schlimmsten Algorithmen, dem originalen (d.h. unbeschleunigten) Bogo- und dem ziemlich ähnlichen orginalen, also ebenso unbeschleunigten Bozosort hinzu.

Doch nicht alle Sortierungsalgorithmen sind so simpel, nur auf Vergleichen und Vertauschungen aufzubauen, Stichwort: Spezielle Sortieralgorithmen, aber auch Heap- und Smoothsort. Besser wäre es wohl auch nicht mit AVL- und B-Sort, die ich nicht implementiert bekomme. Nicht umsonst habe ich Prozeduren namens Verschiebe und Einzelwertverschiebe dabei!

Aussagekräftig wären solche Werte nur, wenn man sie vergleicht. Also erstmal irgendwo abspeichern. Von einer Messagebox aus lassen sie sich nicht kopieren. Also in ein Editfeld oder, noch besser, in ein Memo oder eine Stringliste hineinschieben? Mir alles viel zu umständlich - es sprengt den Rahmen eine Sortierdarstellungs- bzw. visualisierungsprogrammes bei weitem!

Horst_H hat folgendes geschrieben :

Vielleicht in einer Unterabteilung als Vergleich verschiedener "vernünftiger" Sortierverfahren.

Für Lehrzwecke ist alles „vernünftig“. Als Nichtinformatiker lehne ich mich nicht so weit hinaus, hier Festlegungen zu treffen. Die Anforderungen an Sortieralgorithmen sind in der Praxis auch unterschiedlich, so daß es hinsichtlich der Umgebung(sbedingungen) geeignetere und weniger geeignete gibt.

Horst_H hat folgendes geschrieben :

Wenn Du es richtig eilig hast, könnte das Zeichnen horizontaler, statt vertikaler, Linien schneller sein.

Wenn man es eilig hat (keine günstige Voraussetzung für ein „Kurzfilmkino“!), bricht man ab und verkleinert das Fenster vor der nächsten Darstellung. Da Monitore eher breit als hoch sind, schränkt, Dein Vorschlag angewandt, das die Maximalanzahl darstellbarer zu sortierender Elemente (darauf kam es mir an, s.o.) unnötig ein.
Unsere Augen (Gesichtsfeld) als auch unser Gehirn sind zudem für die Wahrnehmung horizontaler Bewegungen besser geeignet.

Gruß Delphi-Laie

Nach diversen kleinen Fehlerbehebungen habe ich meinen Programmen nunmehr eine kleine funktionale Erweiterung spendiert: Beim Sortierformular änderte ich den Borderstyle so, daß es nunmehr ein echtes Fenster (also mit Rahmen) ist.

Wird die Anzahl der Zeilen und Spalten hinreichend klein gewählt, sodaß das Formular auch mit Rahmen in den Bildschirm paßt, dann wird der Fenstermodus automatisch, also immer zugeschaltet (was mir auch sympathischer ist). Ist das Sortierformular gleich groß oder nur unwesentlich kleiner als der Bildschirm, sodaß der Fensterrahmen eigentlich nicht mehr hinzupaßt, dann läßt sich der Fenstermodus jedoch erzwingen - was dann aber geringfügig zu Lasten der verfügbaren Spalten- und Zeilenanzahl und damit der Anzahl der zu sortierenden Elemente geht. Der (logischerweise rahmenlose) Vollbildmodus ist also weiterhin möglich.

So, zum (vorläufigen?) Finale die absolute Krönung: Die beiden (derzeit) schnellsten (allgemein anwendbaren) Sortieralgorithmen AVL- & B-Sort (vorgestellt von Peter Weigel auf Sortieralgorithmen(.de)) fügte ich in mein Programm ein!

Optisch sind diese zwar kein Hochgenuß/Leckerbissen, bedienen dafür aber alle Komplexitäts- und Geschwindigkeitsfanatiker. Schon die Visualisierung läßt erkennen, daß sie in einer anderen Liga als Heap-, Merge- und sogar Quicksort spielen und eher der Geschwindigkeit der speziellen Sortieralgorithmen bzw. Bucketsorts entsprechen.

Auch an dieser Stelle danke ich dem Forum www.planet-quellcodes.de, dort speziell der Delphi/Kylix-Rubrik, wo das schon vor Jahren mal (erfolglos?!)thematisiert wurde, ich das deshalb dort wieder aufgriff und man mich bei der Portierung von C nach Objektpascal massiv unterstützte.

Weiß nicht ob das jetzt schon genannt wurde, ist auch nur ein visueller fehler,
Der Beadsort hat irgendwie einen schönen farbverlauf wenn er fertig mit sortieren ist anders als die anderen Verfahren ;x
Bei Distribution Counting das selbe
Bei Strait Radix ebenfalls
Bei Slowsort friert das programm ein

Hallo,

ich möchte nur anmerken, dass die Laufzeit der Verfahren nicht unbedingt etwas mit der Laufzeit der visuellen Darstellung zu tuen haben, da nur Tauschungen dargestellt werden.
Selection-Sort ist von der Laufzeit her quadratisch in n, läuft aber fixer als heap-Sort in der Visualisierung, da ja genau einmal pro Durchgang getauscht wird, ist also von daher also optimal.
Die Vergleiche fehlen.
Beim AVL Baum sieht die Visualisierung aus, wie Selection-Sort.Da erkenne ich keinen inneren Ablauf des Verfahrens bei der Visualisierung.
Vielleicht ähnlich:
www.inf.ethz.ch/pers...s/SortAnimation.html

Also neben jedem Wert eine Spalte, sodass zum Beispiel neben dem Wert1 gegen den gerade verglichen wird, ein gelber Strich auftaucht und neben Wert2 ein grüner.Der rote Strich neben dem Wert der fertig positioniert ist.Das müsste bei Quick-Sort das Partitionieren noch anschaulicher machen können.

Aber Heap/AVL lässt sich auch schlecht darstellen, da ja die Baumstruktur nicht zu sehen ist.

Übrigens sieht OetSort bei mir einfach phantastisch aus

Gruß Horst

Danke für Eure Reaktionen!

Niko S. hat folgendes geschrieben :

Weiß nicht ob das jetzt schon genannt wurde, ist auch nur ein visueller fehler, Der Beadsort hat irgendwie einen schönen farbverlauf wenn er fertig mit sortieren ist anders als die anderen Verfahren ;x Bei Distribution Counting das selbe Bei Strait Radix ebenfalls

Das schrieb ich oben, ist aber zugegebenermaßen bei der Fülle der Informationen (wer liest das?) leicht zu überlesen: Die speziellen Sortieralgorithmen können die Farbinformation nicht behalten. Das ist weder ein Fehler in meinem Programm noch in den Algorithmen, sondern liegt am Wesen dieser Algorithmen selbst. Mit der Schwarz-(Weiß-)Variante (Farbe abschalten) ist diese gewisse Fehlerhaftigkeit natürlich beseitigt. Ich kann natürlich die Option automatisch umschalten (lassen), doch dann muß der Nutzer danach den - anzunehmenderweise eher gewünschten - Farbverlauf explizit wieder zuschalten. Hat also alles zwei Seiten.

Niko S. hat folgendes geschrieben :

Bei Slowsort friert das programm ein

Nein, tut es nicht, ganz im Gegensatz: Es ist intern, im Hintergrund (nämlich in Form ständiger Stackbeschäftigung) tüchtig am Rödeln und Werkeln, doch das wirkt sich nicht erkennbar auf den Sortierungsfortschritt aus. Es hat doch eine selbsterklärende Bezeichnung. Für derartige Algorithmen am besten wesentlich kleinere Auflösungen (konkret Spaltenanzahl), als der Bildschirm bietet, wählen!

Zu Horst:

Ich hatte AVL- und B-Sort aus Sportsgründen später mit eingefügt. Eingangs schrieb ich, daß ich mich auf die Algorithmen konzentriere, bei denen man halbwegs nachvollziehen kann, wie die funktionieren, was intern abläuft. Da müssen Algorithmen, die die Daten intern in Baumstrukturen anordnen, natürlich passen. Nur bezüglich der Geschwindigkeit sind Sie doch anschaulich.

Apropos Geschwindigkeit. Ja, ich weiß, daß das Laufzeitverhalten letztlich eine Funktion über der Anzahl, der Menge, der Größe, der Komplexität der Eingangsdaten ist. Select(ion)sort ist auch nur elementar und damit von quadratischer Laufzeit, jedoch mit einer sehr geringen Konstante, so daß bei einer Elementeanzahl, die im Bereich der Bildschirmspalten liegt, keine solche Quadrazität gefühlt wird.

Die Zielstellung temporären Farbdarstellungen dürften an der Geschwindigkeit scheitern. Sobald man allerdings die Bremse ein wenig überzieht (deswegen mein diesbezüglicher warnender Hinweis auf dem Formular), wird es quälend langsam. Mag sein, daß man Quicksort damit noch anschaulicher gestalten kann, nur ist es das Ziel meines Programmes, eine möglichst große Bandbreite von Sortieralgorithmen darzustellen: Nicht alle Algorithmen funktionieren auf der Basis von Vergleichen und/oder Vertauschungen.

Horst_H hat folgendes geschrieben :

Hallo, das sieht ja mächtig bunt aus

Richtig bunt ist es (erst) ab heute. Auch ansonsten tat sich (bzw. ich) mit dem Programm in der geraumen Zwischenzeit noch so einiges, wenn nicht gar eine ganze Menge...

Hallo,

jetzt weiß ich wenigstens, warum die Farben manchmal so schön bleiben, Bei beadsort und countsort ..
Dort wird nur der Wert/Schluessel rekontruiert, aber nicht die startpos, die für die Farbe verantwortlich ist, was dort ja auch grundsaätzlich nicht geht.
Ich habe mal eine Versuch gemacht, indem statt startpos der Schluessel die Farbe bestimmt.
Ich habe den Record von Menge um col==Farbe erweitert, damit das nur einmal gerechnet werden muss und bei linie_zeichnen einfach genutzt werden kann.
Ich erstelle eine aufsteigend sortierte Folge.

die anschliessend ala Fisher-Yates? gemischt wird.
Alle Sortierverfahren, die die procedure tausche(x,y) nutzen, sortieren dann farblich anschaulich richtig.
Dabei sieht man auch, das AVL-sortiert nicht "stabil" ist, weil gleiche Werte ihre Reihenfolge gewechselt und damit die Farbfolge irgendwie nicht passt. wohingegen selectionsort "stabil" ist.
Um das noch anschaulicher zu machen habe ich bei der Farbauswahl nur schwarz einfach alternierend grün/rot genommen.

Gruß Horst

Hallo Horst, danke! Schön, daß wenistens Du mir die Treue hältst!

Horst_H hat folgendes geschrieben :

Hallo, jetzt weiß ich wenigstens, warum die Farben manchmal so schön bleiben, Bei beadsort und countsort ..

Ich schrieb das bereits oben (allerdings ist es zugegebenermaßen doch sehr viel Text geworden): Die speziellen Sortieralgorithmen zählen einfach nur, von welchem - vorher bekannten!, weshalb es sie wohl (fast?) nur bei integren Größen gibt - Wert jeweils wieviele Exemplare existieren. Damit sind Sortierelement gleichbedeutend mit Sortierschlüssel. Zusätzliche Informationen der Sortierelemente können nicht mit transportiert werden.

Ich sehe aber ein, daß die Farbverläufe bei jenen nach der Sortierung zu Irritationen und Fehlervermutungen führen können, weshalb die Sortierung dieser speziellen Sortieralgorithmen nur noch in/mit Schwarz visualisiert wird. Ich probierte es früher schon, kam aber nicht weiter. Nunmehr gelang es mir aber doch, das so zu implementieren/programmieren, daß es plausibel erscheint (vorher erzeugte die Neuzeichnenprozedur wiederum farbige Balken, was ebenso irritierend gewesen wäre). Leider waren auch in meiner neunen Version wiederum doch einige Fehler (komischerweise auch solche, die eigentlich schon korrekt erstelltem Programmcode entsprachen). Nun müßte es wiederum etwas besser sein, falls nein, freue ich mich über jeden Fehler- oder anderweitigen Verbesserungshinweis. Allmählich wage ich die Vermutung, daß es weltweit kaum noch bessere Sortieralgorithmenvisualisierungen gibt (geben dürfte).

Horst_H hat folgendes geschrieben :

Ich habe mal eine Versuch gemacht, indem statt startpos der Schluessel die Farbe bestimmt. Ich habe den Record von Menge um col==Farbe erweitert, damit das nur einmal gerechnet werden muss und bei linie_zeichnen einfach genutzt werden kann. Ich erstelle eine aufsteigend sortierte Folge. markieren Delphi-Quelltext     1: 2: 3: 4: 5: For x := 0 to pred(Spaltenanzahl) do begin   Menge[x].Startpos := x;   Menge[x].Schluessel := x * Zeilenanzahl DIV Spaltenanzahl;// Da Zeilenzahl meist kleiner Spaltenzahl , ergeben sich doppelte Werte ( bei mir 1080 /1920 also etwa 44 % )   Menge[x].col := f(Schluessel, Ausgewähltes Farbspectrum);   end; die anschliessend ala Fisher-Yates? gemischt wird.

Du gehst ja vehement an diese meine Sache.... Alle Achtung....wenn ich mal diese Ausdauer und Voraussetzungen hätte, mich in fremder Leute Quelltexte einzulesen.... Diese ständige und teilweise eigentlich redundante Rechnerei vor jedem Liniezeichnen gefiel mir auch von Anfang an nicht (allerdings sind das alles doch ziemlich schnelle Integeroperationen), aber die Farbe mitzutransportieren, ging ich als Herausforderung noch nicht an. Allerdings dürfte das Tauschen der Sortierelemente, wenn diese größer werden, die Algorithmen auch eher verlangsamen. In der Praxis sind die Sortierelement meistens ziemlich groß und komplex, so daß i.d.R. wohl nur die Zeiger bzw. Indizes verändert/getauscht/verschoben werden. Doch um 'all das ging und geht es mir nicht, sondern um die Visualisierung. Bei einem Programm dieser Größenordnung - mit dem man allerdings "mitwächst" - bin ich als Laien-Freizeit-/Hobby-Programmierer ohnehin immer an der oberen Grenze meines Könnens und meiner Überschaufähigkeiten, so daß ich jede weitere Verkomplizierung und Quellcodevergrößerung vorher ernstlich bedenke und abwäge.

Hallo Horst!

Zufallspermutationserzeugung nach Fisher-Yates sowie die Farbberechnung nunmehr schon bei der Erzeugung der Startmengen (es bleibt dabei: Jedem Balken seine eigene Farbe) sind jetzt implementiert.

Danke für diese Deine Anregungen!

Hallo,

das ist noch nicht so,wie ich mir das vorstellte.
Am Ende sollte die Sortierung farblich harmonisch sein
In der procedure Mischen hab ich direkt zu Beginn die Farben zugeordnet.
Die Farbzuordnung zum Schluß kann dann weg.

Mit Fisher-Yates soll es dann gemischt werden, das ist schon dann schon Zufall.

Die Lazarusversion bleibt bei mir oft hängen
Ab Version 9.29 ? muss in der *.lpr
//{$IFDEF WIN32}{$R Sortierkino_Lazarus_statische_Arrays.rc}{$ENDIF}
auskommentiert werden.

Gruß Horst

Horst_H hat folgendes geschrieben :

Hallo, das ist noch nicht so,wie ich mir das vorstellte. Am Ende sollte die Sortierung farblich harmonisch sein In der procedure Mischen hab ich direkt zu Beginn die Farben zugeordnet. Die Farbzuordnung zum Schluß kann dann weg.

Gut, das Prinzip klar. Eben war ich noch fast geneigt, das als (Farb-)Spielerei abzutun, besann mich aber daran zurück, warum ich die Farbvariante einführte. Analogieschluß: Dann kann man vor der Sortierung schon erkennen, wo das Sortierelement am Ende der Sortierung stehen sollte, besser muß, und hat dann am homogenen Farbverlauf eine zusätzliche Bestätigung der Korrektheit des (jeweiligen) Algorithmus' (man sieht das aber auch an der oberen Linie). Doch das kann man doch anhand der Länge, die symbolisch und und als Maß für die Größe des Sortierschlüssels steht, schon erkennen. Mir ging es ursprünglich darum, daß das Sortierelement die Information über seine Startposition im Verlaufe der Sortierung behält ("mit sich herumschleppt"). Da die Längen der Balken das nicht können, blieb die positionsabhängige Einfärbung als einzig mir noch möglich erscheinende Visualisierungsinformation übrig.

Also, das entspricht nicht meiner Intention, aber da ich meinen Quelltext zur Verfügung stelle, sind Veränderungen/Erweiterungen jederzeit möglich.

Horst_H hat folgendes geschrieben :

Die Lazarusversion bleibt bei mir oft hängen Ab Version 9.29 ? muss in der *.lpr //{$IFDEF WIN32}{$R Sortierkino_Lazarus_statische_Arrays.rc}{$ENDIF} auskommentiert werden.

Was bleibt hängen - das Compilieren oder das Laufenlassen der Compilate?
Version 0.28.2 compiliert bei mir tadellos, die - bei mir funktionierenden - Compilate liegen bei. Jedoch schafft es keine der mir vorliegenden 64-Bit-Versionen (und ich habe schon die (immer noch?) aktulle, das zu kompilieren, die Compilierung bleibt hängen, und zwar wegen der von Dir schon zitierten Zeile (wie ich in mühevoller Suche herausfand). Deshalb änderte ich den Compilerschalter auch von "Windows" nach "Win32", womit der Befehl dann natürlich ignoriert wird und nichts mehr hängebleibt. Also, Ikonen bekommt Lazarus 64 Bit immer noch nicht eingebunden. Natürlich hätte ich ikonenfreie Compilate beilegen können, doch sind die 64-Bit-Compilate ja noch ca. 1,5mal so groß wie ihre 32-Bit-Pendants.

Nach Lazarus portierte ich diese Programme, um zwei Fragen beantwortet zu bekommen, die ich beide nur mit Augenmaß (fast im wahrsten Sinne des Wortes) und "gefühlt" beantworten kann:

1. Sind Lazarus-Compilate langsamer als die des Delphis? Wann ja, dann nur geringfügig.
2. Sind 64-Bit-Compilate schneller als ihre 32-Bit-Pendants? Das untersuchte ich bisher noch weniger, aber vom ersten Eindruck her, eher noch weniger, als sich Frage 1 mit gewisser Treffsicherheit beantworten läßt.

Hallo,

vielleicht sollte man die Startknöpfe blockieren, damit man nicht mehrere Sortiervorgänge aufruft.
Ich habe mal eine andere Art der Sortieranimation, möglichst langsam

Gruß Horst

Horst_H hat folgendes geschrieben :

Hallo, vielleicht sollte man die Startknöpfe blockieren, damit man nicht mehrere Sortiervorgänge aufruft.

Wie, was, bei meinem (meinen) Sortierkino(s)?

Dort wird doch vor dem Start der Sortierung das Sortierstartformular ausgeblendet, sodaß keine Sortierung erneut aufgerufen werden kann, solang man die alte nicht abbricht bzw. diese beendet ist.

Hallo,

ich kam nur drauf, weil bei mir bei der Programmausführung der Lazarusversion mit dem merkwürdigem stockendem Verhalten kam.
Die Darstellung der unsortierten Menge zu Beginn wandert gemütlich von links nach rechts. Wenn ich dann auf der Fläche klicke, wird ja wieder gewechselt,. Wenn ich dann sofort wieder auf Darstellung drücke, wird es dann mal schnell, mal garnicht mehr gezeichnet, oder eben sehr langsam.Nach klicken lande ich im Hauptmenue.
Der Thread von Form2/unit2 ist irgendwie nicht zu stoppen.

Irdgendwann ist die Zeichnerei ins Nichts beendet und es piept dann mehrfach.

Die Delphiversion macht das nicht, mit dem Klick ist die Menge auch schon angezeigt.
Einen großen Vorteil Deiner Farbgebung= Stratpos.Es ist mir erst bei der gemischten Folge zweier Werte aufgefallen.
Man sieht ob es stabil ist.Einmal AVl und einmal Heapsort.




Gruß Horst

Hallo Horst, danke erneut!

Dieses "merkwürdige Verhalten" kann ich mit meinen Lazarus-Compilaten nicht nachvollziehen, probiertest Du meine beiligenden Compilate aus, oder ließest Du selbst compilieren? Die Darstellung der unsortierten Startmenge erfolgt bei mir in einem Augenblick, auch bei zugeschalteter Bremse (eben extra noch einmal kontrolliert, auch das mußte ich im Verlaufe der Programmierung irgendwann lösen).

Das einzige, was FPC komplett überfordert, ist das "Rumgemache" mit den Größen width/clientwidth und heigth/clientheight der Formulare, womit ich den Fenstermodus bei Bildschirm(fast)ausnutzung nicht so elegant wie in den Delphicompilaten vom Benutzern zu-/abschalten lassen kann - meine diesbezüglichen Fehlerberichte im Lazarus-Bugtrucker verliefen ergebnislos und die Menge aller meiner Fehlerberichte aus meiner Sicht immerhin noch zu geschätzen 80-90% nicht zu meiner Zufriedenheit. Deshalb ist die entsprechende Checkbox "disabled". Vielleicht schafft das auch FPC irgendwann einmal. Ansonsten haben die Compilate denselben Funktionsumfang und auch (fast) das gleiche Verhalten.

Die Stabilität sieht man am besten bei den beiden konstanten Teilmengen, die voneinander getrennt sind, und zwar links die größere und rechts die kleinere, also mit gespiegelter Startmenge.

Einen Beweis, daß ein Sortieralgorithmus auch bei beliebigen Elementeanzahlen und gar verschieden strukturierten Startmengen immer stabil ist, kann diese Veranschaulichung natürlich nicht bringen/ersetzen.

Gruß

Delphi-Laie

Hallo,

ich habe es extra nochmal mit den beibefügten Kompilaten getestet. Funktiniert genaus so , oder eben nicht

Zur Veranschaulichung der Stabilität reicht es.Beweisen kann man mit tausend Bildern nichts.
Wenn die Startpos in Sortierelement mit gespeichert ist, kann man aber bei beliebiger Ausgangsmenge bam Ende der Sortierung überprüfen, ob dem so war.



Gruß Horst