Bubble-Sort
aus www.iwiki.de, der freien Wissensdatenbank
Bubble - Sort ist ein elementares Sortierverfahren. Es ist einfach zu verstehen und entsprechend einfach umzusetzen. Dieser Sortieralgorithmus wird vornehmlich für kleine Felder verwendet.
Inhaltsverzeichnis |
Prinzip
Die Grundidee des Verfahrens ist es, die unsortiert vorliegenden Daten dadurch zu sortieren, dass immer zwei benachbarte Elemente verglichen und ggf. vertauscht werden. Durch dieses Vorgehen werden also zunächst die Positionen 0 und 1 verglichen, anschließend die Positionen 1 und 2 ...
Durch den Wechsel wird dabei das soeben vertauschte, größere Element direkt in den nächsten Vergleich einbezogen, sodass ein relativ großes Element in einem Durchlauf recht weit nach hinten wandern kann.
Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.
Die Laufzeit steigt mit der Anzahl zu sortierender Elemente. Schlimmstenfalls ist die Anzahl der Durchläufe gleich der Anzahl von Elementen der Folge.
Beispiel
Pseudocode
a1, a2, a3, …, an sind zu sortieren:
FOR i:= 1 TO n-1 DO
FOR j:= 1 TO n-i DO
IF aj > aj+1
THEN tmp:= aj
aj:= aj+1
aj+1:= tmp
END IF
END FOR
END FOR
