Sortieren eines Feldes der Mächtigkeit n mit Bubblesort

Letztmalig dran rumgefummelt: 28.05.20 14:21:36

	Bubble-Sort - das Prinzip der aufsteigenden Blasen - ist der Klassiker unter den Sortieralgorithmen überhaupt - wer noch nie sortiert hat, kommt genau damit geradezu zwangsläufig als erstes in Berührung. Zwar ist er nicht sehr effizient, aber seine Logik ist simpel und auch eine Programmierung zumindest auf Hochsprachenniveau recht einfach und vor allem erfolgversprechend.
	1. Problembeschreibung sowie Lösungsansatz mit verbaler Beschreibung 2. Lösungsalgorithmus und -varianten 3. Programmstrukturen und -möglichkeiten 4. Verwandte Themen
	Praktische Elementaralgorithmen das Bubble-Sort-Logo begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Zeitkomplexität Worst-Case-Denken der "Worst-Case" liegt hier in der Struktur der bereitgestellten Werte, für welche später Algorithmen erstellt werden sollen Laufzeitproblematik Effizienz Effiektivität
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer

1. Problembeschreibung sowie Lösungassansatz

	Eine in ihrer Anzahl beliebig gegebene Menge (theoretisch größer als 2) von Elementen soll sortiert werden. Wird die Menge mächtig, so ist der hier vorgestellte Algorithmus aufgrund seines Aufwandes nicht besonders vorteilhaft.
	auf- sowie absteigende Folgen sollen eingeschlossen sein
	der Beginn einer sortierten Folge soll zufällig sein
	gleiche Elemente sollen generierbar sein

2. Lösungsalgorithmus und -varianten

	Im einfachsten Falle wird einfach n-1 mal "durchgebubbelt" und dies auch n-1 male wiederholt. Das ist eine grundsätzlich richtige Lösung, welche zu einem absolut korrektem Ergebnis führt. Erst genaueres Betrachten der Zwischenergebnisse zeigt, dass enorme Mengen an absolut unnötigen Schritten absolviert werden. So steht nach einem "Durchbubbeln" zumindest eines der größten Elemente definitiv auf der letzten Stelle - muss also in den Folgedurchläufen gar nicht mehr in die Betrachtung einbezogen werden.
	verbale Beschreibung des Lösungsalgorithmus: Beginnend beim kleinsten (sukzessive größten) Element beginnend, werden jeweils zwei benachbarte Elemente verglichen und in dem Falle, dass auf dem größeren Platz das kleinere Element steht, ausgetauscht. Die geschieht bis zum vorletzten Element der Menge und wird anschließend einmal weniger wiederholt, wie es Elemente gibt.
	Verringerung des Aufwandes zum Grundalgorithmus (das ändert nichts an der Tatsache, das der Aufwand n-polynomial bleibt) Konstruktion der inneren Schleife so, dass sie bei jedem Durchlauf ein Element weniger analysiert, da ja jeweils ein maximales Element nach hinten rutscht Durchbubblen von beiden Seiten (das größte schiebt nach oben, gleichzeitig das kleinste nach unten - dies reduziert die Anzahl der äußeren Schleifendurchläufe auf die Hälfte) Einbau einer Testvariable, ob im letzten Durchlauf überhaupt getauscht wurde - wenn nicht, dann ist das Feld bereits sortiert und der Algorithmus kann abgebrochen werden ;-)
	Bubble-Sort auf den Delphi-Seiten von Herrn Heisrath Bubble-Sort mit Assembler programmiert
	grafische Lösung des Grundalgorithmus Bubble-Sort grafische Lösung des Grundalgorithmus Bubble-Sort als ZIP-Archiv grafische Lösung des Grundalgorithmus Bubble-Sort als ZIP-Archiv grafische Lösung des Grundalgorithmus Bubble-Sort als ZIP-Archiv

3. Programmstrukturen und Lösungsmöglichkeiten

	Die Effektivität des Programms liegt in der Verwendung einer Konstante zur Dimensionierung des Feldes - das lässt sich unter Umgehung der Deklarationen für Standard-PASCAL noch effizienter gestalten, indem eine dynamische Dimension des Arrays angenommen und der jeweils gültige Wert abgefragt wird.
	Der Bubble Sort bietet neben seiner "einfachen" Verständlichkeit sehr gut Ansätze, nachweisbar und logisch nachvollziehbar seine Effizienz zu steigern: gleichzeitig in einem Durchlauf oben und unten Bubbeln lassen - dies reduziert die Anzahl der Durchläufe mit jeweils neu zu berechnendem Index um die Hälfte nach einem inneren Schleifendurchlauf ist mit Sicherheit das letzte Element eines der möglichen größten und braucht folgerichtig bei weiteren Durchläufen nicht mehr mit verglichen werden - das gewinnt nochmals Laufzeiteffizienz, wenn gleichzeitig von oben und unten her gearbeitet wird eine Kontrollvariable wird mitgeführt und entscheidet nach einem Durchlauf, in welchem nicht getauscht wurde über den Abbruch, denn dann ist das Feld bereits sortiert Programm-Modul zum Füllen eines Feldes mit standardmäßig 100 Buchstaben virenfreier Download der kompletten EXE-Datei   Quelltext des Programms als ZIP-Archiv
	... in der Oberfläche sehen die Algorithmen alle gleich aus - ihre wahre Bedeutung steckt in den jeweiligen Kernprozeduren ... absolut einfach - mit maximalem Aufwand jedoch funktionstüchtig ... einfach - berücksichtigt jedoch bereits absolut definierte "Teilsortierungen" ... logisch ausgeklügelt - erkennt nach maximal einem beschäftigungslosen Durchlauf, dass nichts mehr zu sortieren ist   ... absolut unintelligenter Bubble-Sort virenfreier Download der kompletten EXE-Datei Quelltext des Programms als ZIP-Archiv ... logisch-ökonmischer Bubble-Sort virenfreier Download der kompletten EXE-Datei Quelltext des Programms als ZIP-Archiv ... logisch-intelligenter Bubble-Sort virenfreier Download der kompletten EXE-Datei Quelltext des Programms als ZIP-Archiv   alles, was falsch laufen kann läuft hier falsch es müssen unbedingt und in jedem Falle n-1 n-1 Durchläufe durchgeführt werden die Aufgabe selbst jedoch wird gelöst - mit Sicherheit und immer der Aufwand zur Lösung beträgt unabhängig von den Eingangsbedingungen her gesehen, das Maximum - die Laufzeit für große Anzahlen von Elementen wird leicht "überproportional"! es werden nicht mehr unbedingt n-1 n-1 Durchläufe durchgeführt dieser Algorithmus verarbeitet bereits die Tatsache, dass nach einem Durchlauf unter allen Bedingungen zumindest eines der "größten" Elemente auf dem letzten Platz steht es werden den ursprünglichen n-1 n-1 Durchläufen lediglich noch die als Sortierung durchgeführt, welche mindestens ein Vertauschung bringen - keine Vertausch bedeutet ja genau: das Feld ist sortiert es gibt maximal an Aufwand einen letzten Durchlauf, in welchem keine Vertauschung mehr durchgeführt wird im statistischen Mittel auf eine Vielzahl von Sortierungen auf gigantisch große Datenfelder ist das nach 50 % der Durchläufe der Fall
	Aufwandsbetrachtung des Algorithmus: Anzahl der Vergleiche: Anzahl der Vertauschungen Anzahl der Zuweisungen: Anzahl der Durchläufe Witz des Themas - hier: Sortierkriterien: Sebastian kommt am frühen Morgen zu seiner Mama gelaufen: “Mama, ich habe gerade fünf Fliegen gefangen. Drei Weibchen und zwei Männchen.” “Und wie hast Du gewusst, welche Männchen und welche Weibchen sind?”, fragt ihn Mama. “Ganz einfach: Drei sind auf dem Spiegel gesessen und zwei auf der Bierflasche.”

4. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Quick-Sort Shaker-Sort MINIMUM- bzw. MAXIMUM-SORT - auch als Selection-Sort bekannt Merge-Sort Bucket-Sort Index-Sort Shell-Sort Distribution Sort (Einführung in die Informatik) Radix-Sort Simple-Sort Field-Sort Heap-Sort
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost August 2006