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.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