Informatik für Anfänger: Sortieralgorithmen (Teil 1: InsertionSort)

Wer kennt es nicht? Man hat eine Liste von Zahlen vor sich und fragt sich, wie man diese sortieren kann. „Das ist doch einfach?“ ist wahrscheinlich der erste Gedanke, den ihr haben werdet, aber dem ist leider nicht so. Viele überschätzen die Fähigkeiten eines Computers und können sich gar nicht vorstellen, wie der es macht. Dazu gibt es eine Reihe von Sortieralgorithmen, von denen ich Nach und Nach einen vorstellen werde. Wir fangen an mit „InsertionSort“.

InsertionSort ist eines der einfachen Sortieralgorithmen. Im Prinzip kann man es sich so vorstellen: Wir geben dem Computer eine Liste mit unsortierten Zahlen, in diesem Beispiel 4|3|5|1|6|2, und dieser fügt die Werte in richtiger Reihenfolge in eine sortierte Liste ein. In dem Falle vom oben genannten Beispiel nehmen wir also zunächst die 4 und fügen sie in die sortierte Liste ein. Danach die 3, welche kleiner ist als 4 und somit davor muss, dann die 5, etc. Das folgende Bild illustriert einmal die Schritte, die zeigen sollen, wie InsertionSort funktionier.

Hier zeige ich einmal die Schritte, die zeigen, wie InsertionSort funktioniert.

Was vielleicht auffällt und Thema für einen weiteren Beitrag wäre, ist, dass ich im Bild angemerkt habe, dass InsertionSort eine Komplexität von O(n²) besitzt. Was heißt das in diesem Falle? Damit die Liste sortiert wird, werden n*n Vergleiche benötigt und um die Werte richtig in die sortierte Liste einzusetzen, müssen insgesamt n*n Vertauschungen vorgenommen werden. Bleibt also O(n²) + O(n²). Genauer möchte ich auf dieses Thema in dem Moment nicht eingehen, aber bei der O-Notation ist es egal, ob man es als O(n²)+O(n²) oder als O(n²) schreibt und somit benutzen wir letztere Schreibweise (Mathematiker sind in aller Regel faul 😉 ).

Solltet ihr Fragen haben oder etwas nicht verstanden haben, könnt ihr euch gerne melden oder kommentieren. Ansonsten geht es nächstes Mal mit „SelectionSort“ weiter!

Thomas

Ich bin Fan von allen technischen Produkten. Marke? Egal! Hauptsache es funktioniert rund!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.