Sortieren eines Feldes der Mächtigkeit n mit Indexsort

Letztmalig dran rumgefummelt: 30.03.10 05:55:21

	Index-Sort - das Prinzip der Verwaltung der "Verweise" - ist der Klassiker unter den Sortieralgorithmen für Datenbanken - wer eine "mächtige" Datenbank sortieren muss, kommt genau damit sehr schnell in Berührung. Er ist für große Datenmengen sehr effizient und in seiner Logiksimpel - und auch eine Programmierung zumindest auf Hochsprachenniveau recht einfach und vor allem erfolgversprechend.
	1. Problembeschreibung 2. Lösungsalgorithmus und -varianten 3. Programmstrukturen und -möglichkeiten 4. Verwandte Themen
	Praktische Elementaralgorithmen das Index-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
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer

1. Problembeschreibung

	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 besonders vorteilhaft - zumal eine Sortierung in Praxis aufgrund der großen Datenmenge nicht auf dem Speicher (RAM und somit schnell) erfolgt, sondern es wird auf externen Datenträgern - häufig noch weit entfernt (Netzwerke) sortierend zugegriffen.
	Physischeses Sortieren - unpraktisch für große und verteilte Datenbasen unsortiertes Ausgangsfeld sortiertes Ausgangsfeld Datensatz angefügt Feld neu indiziert
	Indexsequentielles Sortieren - nur die nach aktuell stehenden Tupel werden im Index incrementiert - das geht schnell unsortiertes Ausgangsfeld sortiertes Ausgangsfeld Datensatz angefügt Feld neu indiziert
	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.
	Programm-Modul zum Füllen eines Feldes mit standardmäßig 100 Buchstaben virenfreier Download der kompletten EXE-Datei   Quelltext des Programms als ZIP-Archiv
	Aufwandsbetrachtung des Algorithmus: Anzahl der Vergleiche: Anzahl der Vertauschungen Anzahl der Zuweisungen: Anzahl der Durchläufe

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.
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	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 am 28. März 2010 um 16.23 Uhr