Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Bubblesort 1)
 

 
 
Bubble = Blase



Voraussetzung
 
Das Verfahren erhielt seinen Namen wegen der Analogie seiner Arbeitsweise zu aufsteigenden Blasen in einer Flüssigkeit.

Gegeben ist ein Feld A mit n Positionen, also A[0] ... A[n-1], in welches die zu sortierenden Datensätze eingetragen sind.
Mittels A[i].Schluessel können wir auf den Schlüssel des i-ten Datensatzes zugreifen.
 
Die Idee des Verfahrens
 

Die Idee


Durchlaufe das Feld wiederholt von links nach rechts.
Falls von zwei benachbarten Datensätzen der linke Schlüssel größer ist als der rechte,
vertausche die beiden Einträge.
 



Eine praktische Übung
 
Um die Wirkungsweise zu verstehen, solltest du folgende Übung durchführen.
   Lege eine Folge von  Münzen, Spielkarten o.ä. zufällig sortiert vor dich auf den Tisch.

Vergleiche das erste und das zweite Element und vertausche diese falls nötig. Dann vergleiche das zweite und dritte Element usw.

Bergründe warum stets das größte Element nach rechts verschoben wird!

Die Idee wird in folgendem Algorithmus präzisiert.
 
Der Algorithmus
 

Der Algorithmus


für i=0 bis n-2:
    für j=0 bis n-i-2:
       wenn A[j].Schluessel > A[j+1].Schluessel dann:
             vertausche A[j] und A[j+1]
        (jetzt besitzt A[j+1] den größten Schlüssel
         in A[0] ... A[j+1])
    (A[n-i-1] ... A[n-1] ist sortiert, die Schlüssel
     der anderen Datensätze sind kleiner oder
     gleich A[n-i-1].Schluessel)
 
Seite 9/17