Algorithmen und Datenstrukturen

Bubble Sort

Gegeben ist ein Array mit n ganzen Zahlen, das in aufsteigender Reihenfolge sortiert werden soll. Der Bubble Sort ist einer der bekanntesten und einfachsten Algorithmen, um dies zu erreichen – allerdings ist er nicht besonders schnell, weshalb in der Praxis üblicherweise andere Sortierverfahren zum Einsatz kommen.
Video preview
Beim Bubble Sort durchläuft man das Array mehrfach und vertauscht jeweils benachbarte Elemente, wenn diese nicht in der richtigen Reihenfolge sind. Genauer gesagt, wenn , werden die beiden Elemente miteinander vertauscht, sodass das Array schrittweise in eine aufsteigende Reihenfolge gebracht wird.
Nehmen wir als Beispiel das Array a (etwa a = [4, 1, -1, 0, 2, 8]). Wir vergleichen zuerst die ersten beiden Elemente. Wenn sie nicht in Ordnung sind, tauschen wir sie (in unserem Beispiel wird daraus [1, 4, -1, 0, 2, 8]). Dann gehen wir zum nächsten Paar und verfahren ebenso ([1, -1, 4, 0, 2, 8]). Wir wiederholen diesen Vorgang bis zum Ende des Arrays (in unserem Beispiel ergibt sich daraus nacheinander [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → keine Änderung → fertig).
Anschließend beginnt die Schleife erneut am Anfang. Auch hier vergleichen wir wieder die ersten beiden Elemente und tauschen sie gegebenenfalls, rücken dann zum nächsten Paar und so weiter, bis wir erneut am Ende des Arrays angekommen sind. In unserem Beispiel ergibt sich dabei: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → keine Änderung.
Dieser Vorgang wird so lange wiederholt, bis das gesamte Array vollständig sortiert ist:
a = [...]
while True:                                 # läuft, bis das Array sortiert ist
    is_sorted = True                        # wenn wir etwas ändern, setzen wir diese Variable auf False
    for i in range(len(a) - 1):             # Schleife von 0 ... n-2
        if a[i] > a[i + 1]:                 # falls etwas nicht in der richtigen Reihenfolge ist
            is_sorted = False               # => das Array war nicht sortiert
            a[i], a[i + 1] = a[i + 1], a[i] # vertausche a[i] und a[i + 1]
    
    if is_sorted:                           # beende den Prozess, falls 'a' sortiert ist
        break
print(a)
Eine mögliche Optimierung besteht darin, unnötige Durchläufe zu vermeiden:
  • Nach jeder Iteration landen die größten Elemente ganz am Ende des Arrays. Das bedeutet, dass nach k Durchläufen bereits die letzten k Elemente definitiv sortiert sind. Daher kann der innere Durchlauf auf den unsortierten Bereich begrenzt werden:
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = obere Grenze für die innere Schleife
    is_sorted = True                        # wenn wir etwas ändern, setzen wir diese Variable auf False
    for i in range(u):                      # Schleife von 0 ... u-1
        if a[i] > a[i + 1]:                 # falls etwas nicht in der richtigen Reihenfolge ist
            is_sorted = False               # => das Array war nicht sortiert
            a[i], a[i + 1] = a[i + 1], a[i] # vertausche a[i] und a[i + 1]
    
    if is_sorted:                           # beende den Prozess, falls 'a' sortiert ist
        break
print(a)
Im ungünstigsten Fall (wenn das Array anfangs absteigend statt aufsteigend sortiert ist) benötigt der Bubble Sort Operationen. Verglichen mit schnelleren Sortieralgorithmen, die wir später im Kurs besprechen, ist das sehr aufwendig.
Sehen wir uns die Arbeitsweise des Algorithmus in mehreren Beispielen an:
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ do nothing
Extracurricular (interesting video)
Es gibt ein großartiges YouTube-Video von Lines That Connect, das die Funktionsweise von Bubble Sort noch detaillierter erklärt. Besonders spannend ist dabei die Kurve, die sich beim Ablauf des Algorithmus bildet.
Video preview
Video von Lines That Connect – The Bubble Sort Curve.

Challenge

Es nehmen n Personen an einem Wettbewerb teil, die in aufsteigender Reihenfolge ihrer Körpergröße angeordnet werden sollen. Dabei darf pro Schritt nur ein Tausch zwischen zwei benachbarten Teilnehmern durchgeführt werden. Da nur wenig Zeit zur Verfügung steht, soll dies möglichst effizient geschehen.
Dafür soll ein Programm die Indizes der Teilnehmer ausgeben, die ihre Plätze tauschen sollen. Die Indexierung beginnt bei 0.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 1000).
Die nächste Zeile enthält n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ), also die Körpergrößen der Teilnehmer.

Ausgabe

Das Programm soll die Indexpaare, die ihre Plätze tauschen müssen, ausgeben. Jedes Paar soll dabei in einer eigenen Zeile stehen. Gibt es mehrere optimale Lösungen, ist jede mögliche Variante davon akzeptabel.

Beispiele

Input
Output
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Erläuterung

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue