Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

37.1 Langsame Sortierverfahren

37.1 Langsame Sortierverfahren

Wie bereits erwähnt, gibt es unterschiedlich gute Sortierverfahren. Fangen wir zunächst mit den langsameren an. Jene sind nicht nur leicht zu verstehen, sondern auch leicht zu implementieren. Sobald Sie aber mehr als 1000 Elemente Sortieren müssen, rate ich dringend von jenen ab. Unter 1000 Elementen nehmen sich die einzelnen Verfahren nichts (liegt bei den heutigen Rechnern im Millisekundenbereich).

Die folgenden Algorithmen haben die durchschnittliche Laufzeit n2, wobei das n für die Anzahl der Elemente steht. Die benötigte Zeit für die Sortierung, wächst also quadratisch mit der Anzahl der Elemente.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1.2 Selectionsort

37.1.2 Selectionsort

Bei diesem Verfahren wir jetzt z.B. der sortierte Bereich von vorne aufgebaut, wobei er immer mit dem nächst gößeren Element erweitert wird. Dieses nächst größere Element wird durch gezielte Auswahl ermittelt, also selektiert und mit dem ersten noch nicht sortierten Element getauscht.

Dieses Verfahren arbeitet vom Ersten bis zum vorletzten Element. Das letzte braucht logischerweise nicht mehr betrachtet werden, weil es kein kleineres Element mehr geben kann. Schauen wir uns dies wieder an der Grafik an.

Veranschaulichung des Selectionsort Sortierverfahrens

Als erstes wird also das erste Element, nämlich die 6, betrachtet und es wird in der Restliste nach einem Element gesucht, welches zum einen kleiner als die 6 ist und zum anderen noch das kleinste Element überhaupt ist. Die Suche ergibt 1 und so werden die zwei Elemente getauscht.

Im nächsten Schritt wird wieder die 6 betrachtet, weil sie wieder das erste Element im unsortierten Bereich ist. Die Suche findet jetzt die 2 als kleinstes Element und die zwei Elemente werden wieder getauscht.

Auch hier sollte der Rest wieder klar sein und für die Suche gilt wieder genau das gleiche wie für Bubblesort. Auch hier müssen Sie darauf achten, dass Sie nicht unnötig gleiche Elemente tauschen, um eine Vorsortierung nicht zu zerstören.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1.3 Insertionsort

37.1.3 Insertionsort

Bisher waren die Algorithmen immer so konzipiert, dass in jedem Schritten, immer die komplette Liste durchlaufen werden musste und oftmals dann sogar nichts mehr gemacht wurde (außer die vermeintlich unnötigen Vergleiche). Gerade dann, wenn schon eine sortierte Liste vorliegt, brauchen diese Algorithmen trotzdem immer ihre quadratische Laufzeit, obwohl sie effektiv nichts machen. Abhilfe schafft hier Insertionsort, was im optimalen Fall, nämlich der bereits sortierten Liste, nur einmal komplett durchläuft und feststellt, dass die Liste sortiert ist. Somit hat dieses Verfahren im besten Fall lineare Laufzeit. Nur im schlimmsten Fall (umgekehrt sortierte Liste) benötigt das Verfahren auch quadratische Laufzeit. Aber wie funktioniert dieses Verfahren jetzt?

Insertionsort fängt immer an der zweiten Position an, wobei angenommen wird, das alles was davor ist, sortiert ist. Nun wird das aktuell betrachtete Element immer in diesen sortierten Bereich gezielt eingefügt. Im Fall einer Liste geschieht dies durch das umhängen von Pointern. Im Falle eines Arrays muss das Element so lange nach vorne getauscht werden, bis es an der richtigen Stelle steht. Um diese richtige Stelle zu finden, muss man jetzt aber nicht immer bis ganz nach vorne laufen. Da alles davor schon sortiert ist, muss man nur dann noch weiter nach vorne laufen, wenn das Element vor dem aktuell betrachteten, größer ist als das aktuelle. Im Fall einer Vorsortierten Liste, wird dies also nie auftreten und das erklärt die lineare Laufzeit. Schauen Sie sich auch hier wieder das entsprechende Beispiel an.

Veranschaulichung des Insertionsort Sortierverfahrens

Zuerst wird die 1 betrachtet und so lange nach vorne gelaufen, bis ein Element gefunden wird, welches nicht mehr größer ist. Die 6 ist größer und da vor ihr kein Element mehr kommt, also auch kein Element mehr größer ist, wird die 1 vorne eingefügt.

Im zweiten Schritt wird jetzt die 7 betrachtet und es wird festgestellt, dass das davor stehende Element kleiner ist, woraus zu schlussfolgern ist, dass davor nur noch kleinere Elemente kommen und die 7 somit schon an der richtigen Stelle steht.

Jetzt wird die 2 betrachtet und wieder fast bis ganz vorne verschoben, wobei alle Elemente dazwischen nach rutschen. Die 5 kommt dann anschließend zwischen 2 und 6 und so geht das Spiel weiter bis zum Ende.

Wie Sie sehr schön sehen können, braucht man im Durchschnitt sogar nur noch ein wenig mehr als die Hälfte des sortierten Bereiches zu durchlaufen und somit auch nur noch die Hälfte an Vergleichen. Somit ist Insertionsort in dieser Kategorie der klare Sieger.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1.1 Bubblesort

37.1.1 Bubblesort

Bei diesem Verfahren baut man z.B. den Sortierten Bereich hinten auf, indem man von vorne her immer das größere Element noch hinten blubbern lässt. Anschließend wird das Selbe wieder von vorne gemacht, nur dass man jetzt nur noch zum vorletzten Element läuft, da das Letzte ja jetzt schon an der richtigen Stelle steht. Dies wird so lange gemacht, bis man nur noch ein Element hat. Schauen wir uns dies an nachstehender Grafik an.

Veranschaulichung des Bubblesort Sortierverfahrens

Damit das Prinzip der Blasen besser deutlich wird, habe ich die Liste nicht von links nach rechts, sondern von unten nach oben aufgebaut. Im Ersten Durchlauf wird die 6 mit der 1 verglichen und da die 6 größer ist, werden die Elemente vertauscht, also die 6 blubbert einen Schritt nach oben. Anschließend wird die 6 mit der 7 verglichen und es wird festgestellt, dass nichts getan werden muss, die 6 also nicht weiter hoch blubbert. Nun wird die 7 mit der 2 verglichen und da die 7 größer ist, blubbert sie hoch, was zur Folge hat, dass sie nun noch mit der 5 verglichen wird, wobei sie noch weiter hoch blubbert. Am Ende des ersten Durchlaufes ist die 7 bis ganz nach oben geblubbert und verlässt die "Meeresoberfläche", also den unsortierten Bereich.

Im zweiten Durchlauf setzt jetzt die globale Erderwärmung ein, welche das Meer soweit verdampfen lässt, dass sie unterhalb der 7 ist und der Spaß geht von vorne los. Zuerst wird wieder die 1 mit der 6 verglichen und es muss nichts getan werden. Dann wird die 6 mit der 2 verglichen und blubbert eins hoch, wo sie dann mit der 5, dann mit der 3 und abschließend mit der 4 verglichen wird und somit ganz hoch blubbert.

Der Rest sollte jetzt klar sein, aber eines sollte noch erwähnt werden. Falls man diesen Algorithmus implementiert, sollte man die vergleiche immer mit dem kleiner oder größer Operator realisieren. Wenn man z.B. kleiner gleich benutzt, kann es vorkommen, dass z.B. 2 "gleiche" Elemente getauscht werden. Nun werden Sie sich fragen, was daran so schlimm sein soll? Nun, stellen wir uns eine Datenbank vor mit einer Adresstabelle. Angenommen wir haben zuerst die Ansicht nach dem Alter sortiert und wollen jetzt die Liste nach den Vornamen sortieren. Normalerweise erwarten wir, dass jetzt Hans Müller und Hans Meier noch nach ihrem alter sortiert sind. Vertauschen wir also den einen Hans mit dem anderen Hans, dann zerstören wir die Vorsortierung. Man nennt Sortieralgorithmen die so etwas machen, instabile.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012