Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Bubble-Sort

Bubble-Sort ist das einfachste Sortierverfahren, es ist "in-place" und die Anzahl der Elemente bleibt erhalten.

Beispiel:

Es werden nur die Vertauschungen angegeben und zwar sind die Elemente hervorgehoben, die gerade getauscht worden sind.

Das unsortierte Feld:	2 5 9 8 1 5 2 4
Wir gehen jetzt das Feld der Reihe nach durch. Sind 2 Elemente in der falschen Reihenfolge, werden diese getauscht.	2 5 8 9 1 5 2 4
	2 5 8 1 9 5 2 4
	2 5 8 1 5 9 2 4
	2 5 8 1 5 2 9 4
Damit ist die größte Zahl an die letzte Stelle gekommen:	2 5 8 1 5 2 4 9

Wir fangen wieder von vorn an. Das erste getauschte Paar ist:	2 5 1 8 5 2 4 9
	2 5 1 5 8 2 4 9
	2 5 1 5 2 8 4 9
Damit ist die 2. größte Zahl an der vorletzten Stelle:	2 5 1 5 2 4 8 9

Wir fangen wieder von vorn an.	2 1 5 5 2 4 8 9
	2 1 5 2 5 4 8 9
Jetzt ist die drittgrößte Zahl an der 3. Stelle von hinten.	2 1 5 2 4 5 8 9

Wir fangen wieder von vorn an.	1 2 5 2 4 5 8 9
	1 2 2 5 4 5 8 9
	1 2 2 4 5 5 8 9

Das Programm zum Sortieren mit Bubble-Sort sieht so aus:

Programm

feld = [2,5,9,8,1,5,2,4]

#Ausgabe des unsortierten Felds
for a in feld:
    print(a,end=' ')
print('\n')

#sortieren mit Bubble-Sort
anzahl = len(feld)
for j in range(0,anzahl):
    for i in range(0,anzahl - j -1):
        if feld[i] > feld[i+1]:
            help = feld[i]
            feld[i] = feld[i+1]
            feld[i+1] = help

for a in feld:
    print(a,end = ' ')

Der Aufruf sah bei mir so aus:

Aufgaben

Bringen Sie das Programm zum Laufen.
Kommentieren Sie die Zeilen 10 bis 15 (das eigentliche Sortieren).
Was bewirkt in der Zeile 11 bei "anzahl - j - 1" das "j"?
Ändern Sie das Programm so, dass die Elemente gewürfelt werden.
~~Ändern Sie das Programm so, dass die Anzahl der Elemente in einer Variablen angegeben werden.~~
Ändern Sie das Programm so, dass die Anzahl der Elemente als Parameter übergeben wird.
Ändern Sie das Programm so, dass die gewürfelten Zahlen im Bereich 100 bis 900 liegen.
Gestalten Sie die Ausgabe attraktiver.

Weblinks

Wikipedia: Bubblesort

zurück