Elementare Sortierverfahren sind Suchalgorithmen aus der Informatik. Hier wird das Thema einfach und verständlich erklärt. Anhand von Beispielen mit Abbildungen und (Java)-Code kläre ich dich kurz und übersichtlich mit den wichtigsten Infos zu den folgenden 3 Algorithmen auf:
- Insertion Sort
- Selection Sort
- Bubble Sort
Unterschieden werden diese Sortieralgorithmen noch einmal in zwei verschiedenen Kategorien. Und zwar „Internes Sortieren“ und „Externes Sortieren“.
Inhaltsverzeichnis
Der Unterschied dabei ist, dass
- beim internen Sortieren der Datenbestand während des Sortierens im Hauptspeicher ist, d.h alle Elemente sind zugreifbar
Beispiel ⇒ Sortieren von Arrays - beim externen Sortieren der überwiegende Teil der Daten während des Prozesses auf externem Speicher ist, z. B. auf Festplatte, Magnetband oder ähnliches. D.h von jedem Stapel sind nur die obersten Elemente sichtbar.
Beispiel ⇒ Sortieren von sequentiellen Files
Wo benötigt man überhaupt solche Sortieralgorithmen?
Dafür gibt es viele Anwendungen, auch wenn einem auf den ersten Blick vielleicht keine einfallen.
Man kann dadurch z. B. in Programmen Daten nach Datum, Kundennummer, Name usw. sortieren. Oder zum Beispiel auch Waren in Online Shops nach Preis usw.
Methoden der Auswahl
Zudem wird noch bei der Methode der Auswahl unterschieden.
Zum einen gibt es die interaktiven Verfahren.
Das bedeutet es wird durch Auswahl, Einfügen und Austauschen sortiert. Ein „Objekt“ wird also ausgewählt und dann an einer richtigen Stelle eingefügt oder mit einem anderen Objekt ausgetauscht. Dies wird so lange gemacht, bis die Daten sortiert sind.
Und es gibt noch das Rekursive Verfahren.
Dazu gehört z. B. der Sortieralgorithmus „Quicksort“. Bei dieser Methode werden die Daten zuerst in Teile zerlegt und dann durch Tauschen sortiert. Wie das aussieht, erfährst du im Beitrag zum „Sortieralgorithmus Quicksort“. Rekursive Verfahren werden in diesem Beitrag hier noch nicht behandelt.
Sortieren durch Einfügen – Insertion Sort
Nun wissen wir schon einiges über Insertion Sort aus der Einführung, z. B. dass es zu den interaktiven Verfahren gehört. Aber auch schon aus unserem Leben kennen wir diese Art der Sortierung. Denn die meisten von uns haben sie vermutlich schon einmal angewandt – Beim Karten spielen.
Wenn du ein Kartenblatt auf der Hand hast, suchst du dir normalerweise die größte oder die kleinste Nummer aus und legst sie an den Anfang. Dann die zweitkleinste/größte usw. Dabei wendest du Insertion Sort an.
Sortierung am Beispiel
Das hier ist nun unsere Liste die wir sortieren möchten.
[9][0][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Wir möchten die Elemente aufsteigend sortieren – Also von der kleinsten Zahl bis zur größten Zahl. Die erste Zahl dieses Strangs ist direkt unser sortierter Bereich und wird daher einfach stehen gelassen und nicht angerührt.
[9][0][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Wir beginnen also mit dem zweiten Element, der „0“. Wir vergleichen sie mit dem ersten Element aus unserem sortierten Bereich, der „9“ und platzieren sie auf der linken Seite vor die neun, weil sie kleiner ist.
So sieht unsere Liste nun nach dem ersten Durchgang aus:
[0][9][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Wir vergleichen jetzt die nächste Zahl wieder mit der linken Zahl aus dem sortierten Bereich. Wie es aussieht ist die „26“ größer als die „9“ und daher kann die neun da bleiben, wo sie ist.
[0][9][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Kommen wir jetzt zur „14“. Wir vergleichen sie mit der 26 und stellen fest, dass sie kleiner ist. Also vergleichen wir sie mit der nächsten Zahl im sortierten Bereich – das ist die „9“. Wie wir sehen ist sie größer als die neun, daher rücken wir die „26“ nach rechts und platzieren die „14“ hinter die „9“.
[0][9][14][26][45][4][12][78][23][31][14][9][0][34][17][26]
Nun kannst du die Liste zur Übung Schritt für Schritt selbst sortieren, sodass sie am Ende so aussieht:
[0][0][4][9][9][12][14][14][17][23][26][26][31][34][45][78]
Funktionsweise des Sortierens durch Einfügen
An der Darstellung oben siehst du vielleicht schon, wie der Algorithmus sortiert.
Man beginnt mit dem zweiten Element des Datensatzes und prüft dann, an welche Stelle es links gehört. Entweder gehört es nun hinter das erste Element oder bleibt vorne.
Dann geht es mit dem 3. Element weiter und es wird geschaut, wo es links hingehört. So fährt man fort, bis die Liste sortiert ist.
Wenn ein Element auf der linken sortierten Seite eingefügt werden muss, so verschieben sich alle Elemente um eine Position nach rechts weiter.
O-Notation – Laufzeit
Best Case O(n)
Worst Case O(n^2)
Average Case O(n^2)
Wieso sind die Laufzeiten so wie sie sind?
Naja, wenn deine Elemente zufälligerweise schon perfekt sortiert sind, dann brauchst du nichts mehr zu verschieben und bist immer nach dem ersten Vergleich schon fertig.
Bedenke dabei, du musst den Vergleich trotzdem mit jeder Zahl ausführen! Sonst würdest du ja auch nicht herausfinden, dass die Elemente schon sortiert sind. Was du dir sparst, ist das Tauschen und Verschieben der Elemente.
Beim schlechtesten Fall musst du genau so oft Tauschen wie du Elemente hast. Da wirklich kein Element an der richtigen Stelle steht.
Sortieren durch Auswahl – Selection Sort
Beim Sortieren durch Auswählen suchst du aus deinem Datensatz das größte Element aus und fügst es an den Anfang oder das Ende (je nachdem, ob aufsteigend oder absteigend sortiert wird).
Hast du dein Element nun an den Anfang (links) gesetzt, so ist das nun der sortierte Bereich. Beim nächsten Durchgang vergleichst du die Elemente rechts davon im unsortierten Bereich und suchst das zweitgrößte Element raus. Dieses wird auch wieder links in den sortierten Bereich nach dem ersten Element gesetzt.
Bei jedem Durchgang verkleinert sich dein Bereich, in dem du vergleichst, um 1. Weil nach jedem Durchgang ein Element in den sortierten Bereich übergeht.
O-Notation – Laufzeit
Best Case O(n^2)
Worst Case O(n^2)
Average CasenO(n^2)
Bubble Sort
Dieses Sortierverfahren kann man sich wegen seines Namens gut merken. Doch wieso heißt es so? Der Name kommt davon, dass in einem Glas Sprudelwasser z. B. die größeren Blasen die kleineren überholen und so als erste aufsteigen. Wenn du dir deine zu sortierende Folge vertikal vorstellst und die Elemente dann nach Größe sortierst, passiert hier das Gleiche.
Sortierung am Beispiel
Für diesen Beispieldurchgang nehmen wir wieder unsere unsortierte Folge von oben:
[9][0][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Jetzt sortieren wir die Zahlenfolge aufsteigend nach dem Bubble Sort Sortieralgorithmus. Dafür vergleichen wir zuerst die „9“ mit der „0“. Da die „0“ kleiner ist, tauschen wir die Plätze.
[0][9][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Jetzt geht es mit der neun direkt weiter, um sie mit Ihrem Nachfolger, der „26“, zu vergleichen.
[0][9][26][14][45][4][12][78][23][31][14][9][0][34][17][26]
Da die „9“ kleiner ist, lassen wir sie an ihrem Platz und nehmen uns nun die „26“ vor. Diese vergleichen wir wieder mit Ihrem Nachfolger. Da 26 > 14 wandert, sie weiter nach rechts, indem sie ihren Platz mit der 14 tauscht.
[0][9][14][26][45][4][12][78][23][31][14][9][0][34][17][26]
Wir vergleichen die 26 nun weiter mit der „45“. Da 26 < 45 bleibt sie an ihrem Platz und wir machen mit der 45 weiter.
[0][9][14][26][45][4][12][78][23][31][14][9][0][34][17][26]
Jetzt kannst du diesen ersten Durchlauf mal selbst zu Ende machen.
Danach müsste deine Folge so aussehen:
[0][9][14][26][4][12][45][23][31][14][9][0][34][17][26][78] Beachte das dies erst 1 Durchlauf war!
Wie du siehst ist die größte Zahl, die „78“ jetzt wie eine Blase aufgestiegen und befindet sich am Ende der Zahlenfolge. Jetzt beginnt der zweite Durchlauf genau gleich. Und das so lange, bis die komplette Folge aufsteigend sortiert ist.
Funktionsweise von Bubble Sort
Wie du indessen hoffentlich gemerkt hast, vergleicht man bei diesem Algo immer zwei nebeneinander liegende Elemente und tauscht diese, wenn nötig, entsprechend aus. Dann vergleicht man wieder die nächsten zwei nebeneinander stehenden Elemente usw.
Wenn dann die größte/kleinste Zahl am Ende steht, ist ein Durchlauf vorbei und alles geht wieder von vorne los.
O-Notation – Laufzeit
Best Case O(n)
Worst Case O(n^2)
Average Case O(n^2)
Zu einem besseren Verständnis kannst du dir die verschiedenen Sortieralgorithmen mal simulieren und beim Sortieren beobachten. Auf dieser Website werden verschiedene Zahlen der Reihe nach sortiert und du kannst den Algorithmus dabei selbst bestimmen.
Schritt für Schritt siehst du nach welchem Kriterium das Element ausgewählt wird und wie es an anderer Stelle eingefügt oder ausgetauscht wird.
Wenn du zu den elementaren Sortierverfahren noch Fragen hast, kannst du diese gerne im Kommentarbereich stellen. Falls noch etwas fehlen sollte, kannst du dies natürlich auch gerne dazu schreiben.
In diesem Beitrag geht es um: Elementare Sortierverfahren
