Sortieralgorithmen

Sortieralgorithmen werden in der Programmierung immer wieder genutzt.
Meist sogar ohne das es der Anweder mitbekommt. Überall wo man Daten nach
Größe, Name oder ähnlichem sortieren kann, werden Sortieralgorithmen verwendet.
Aber auch Versteckte/im Programm integrierte Sortieralgorithemen arbeiten
nach dem selben Prinzip. Und damit möchten wir uns im Folgenden beschäftigen:

Grundsätzlich, arbeiten Sortieralgorithen auf dem selben Prinzip, nämlich
das ein Zeiger das Array durchläuft, und dabei mehrere Vergleiche durchführt.
Je nach Ergebnis des Vergeleichs werden die verglichenen Objekte dann Vertauscht.
Dabei gilt, je inteligenter ein Algorithmus die Vergleiche und Vertauschungen durchführt,
desto weniger Operationen müssen durchgeführt werden, und desto schneller ist der
Algorithmus. Dabei muss er mindestens einmal jedes Objekt verglichen haben.
Manche Algorithmen sind sogar in der Lage ein vorsortiertes Feld zu erkennen,
und dementsprechend Vertauschungen und Vergleiche durchzuführen oder zu lassen.

Mit einigen Beispielen von Sortieralgorithmen und ihrer Erklärung beschäftigen wir uns jetzt.
Beispiele für relativ einfache Sortieralgorithmen sind zum Beispiel:

1. Bubblesort
   Der Bubblesort betrachtet vom gesammten Feld immer nur zwei Vergleichswerte(Bubble).
   Wenn der erste Wert größer ist als der zweite, werden beide vertauscht.
   Um ein Maximal unsortiertes Feld zu sortieren, muss der Algorithmus das
   Feld in der Anzahl der Feldlänge mal zwei durchlaufen, um das Feld
   absolut zu sortieren.(WorstCase, letzte Zahl die kleinste)
2. Simplesort
   Der Simplesort betrachtet immer zwei Zahlen im Feld. Dabei wird vom
   Begin des Feldes an eine Zahl gesucht, die Kleiner ist als die erste
   Zahl des Feld. Wurde eine kleinere Zahl gefunden, wird diese und die
   erste Zahl vertauscht. Wurde auf diese Weise das komplette Feld
   durchsucht, rückt der erste Zeiger auf die zweite Zahl weiter,
   und das Spiel beginnt erneut von Position 2.
3. Selectionsort
   Der Selectionsort verwendet wie der Simplesort zwei Zeiger. Allerdings
   werden nicht stänig Vertauschen durchgeführt, sondern es wird nur nach
   der kleinsten verfügbaren Zahl gesucht. Danach wird diese an den Begin
   des Feldes gesetzt, und ab Positions zwei nach der erneut kleinsten
   Zahl gesucht. Das wird bis zum Ende widerhohlt.
4. Insertionsort
   Insertionsort bediehnt sich einer kleineren programmtechnischen Hilfe
   um die Sortierung zu Beschleunigen. Zwei Zeiger wandern über das Feld
   im Abstand von 1. Sobald eine Zahl gefunden ist, die größer ist als
   ihr direkter Nachfolger, wird die kleinere der beiden in eine Hilfs-
   Variable kopiert, und solange nach einer Zahl links des erstens Zeigers
   gesucht, wie diese größer ist als die Hilfzahl. Wenn gefunden, wird die
   Hilfszahl links von ihrem größeren Partner abgelegt, und alle anderen
   entsprechend Verschoben um die Lücke der Hilfszahl zu füllen.
5. Shellsort
   Shellsort arbeitet wie Insertionsort, allerdings mit dem Unterschied
   das es Anhand von Rastern zuerst nur jedes 5te Feld sortiert, und
   dabei wie Insertionsort vorgeht. Wenn das Sortieren abgeschlossen ist,
   rückt das Raster nach Rechts. Das wird genau 4 mal widerholt. Dann
   wird das Raster auf 3 verkleinert. Selbes Vorgehen, nur mit zweimal
   Weiterrücken. Dann wird das Raster auf 1 verkleinert, ohne weiterrücken.
   Da Vertauschungen zeitaufwendiger sind als Vergleiche, ist diese Verfahren
   Grundsätzlich schneller. Dazu kommt eine ständige Überprüfung ob das
   Feld nicht schon sortiert ist.
6. Quicksort
   Quicksort bediehnt sich einem kleinen Trick. Er benutzt Rekursion.
   Dabei wird das Feld in der Mitte geteilt, und die zahl an der Nahtstelle
   als Vergeleichsobjekt verwendet. Dabei wird jeweils die linke Hälfte
   mit dem Pivot werglichen, wenn zu groß, wird das Element nach Rechts
   vertauscht. Wenn kleiner beleibt alles so. Allerdings ruft sich die
   Funktion an dieser Stelle selbst auf, und unterteilt das Feld erneut
   an dieser Stelle in zwei Hälften.
7. Bucketsort
   Bucketsort greift ein ganz anderes Verfahren zum Sortieren auf.
   So wird ein Zweites Feld mit der Mächtigkeit der Differenz des
   Minimums zum Maximum aufgestellt. Danach wird jede Zahl an die
   Zahl-Minimum Stelle des Feldes geschrieben. Ein Durchlauf und
   das Feld ist sortiert. Allerdings ist Bucketsort Speicherintensiver.

Zum Programm. Das Programm besteht aus einer Grundstruktur zur Generierung
eines Zufälligen, eines Worst-Case, und eines einfachen Falles.
Die entsprechenden zu sortierenden Zaheln werden in einem Array abgelegt, was
dann vom Algorithmus sortiert und in einem Zweiten Array abgelegt wird.
Erst dieses Array wird bei allen gleich ausgegeben.
Im Vergeleich zur Version vom Herrn Rost hat das Programm folgenden Vorteil:
Es ermöglichst das Sortieren des selben Datenbestandes nacheinander mit
verschiedenden Algorithmen. Als Erweiterung ist eine Analyseeinheit vorgesehen,
die die Anzahl der Vergleiche, der Speichervorgänge und so weiter betrachten soll,
um eine Laufzeitbetrachtung durchzuführen.(Gewissermaßen ein Benchmark).
Die Öberfläche besteht ganz simpel nur aus den Bediehnelementen zum Erzeugen
des Arrays, und den verschiedenen Buttons, die die Sortiervorgänge auslösen.
Weiterhin sind zwei Memoboxen für die Kontrolle, das eine ist gefüllt mit
dem zu sortierenden Array, und das andere mit dem Ergebnis der Sortierung.

Download