Bubblesort: benachbarte Werte vergleichen

1. Der zweite Vergleich benutzt die Werte nach dem ersten Tausch.
2. Verfolge die 5: Sie ist jeweils der linke Wert des nächsten betrachteten Paars.

Die Zustände sind [1, 5, 4, 2], [1, 4, 5, 2], [1, 4, 2, 5]. Die 5 wandert bei dieser Laufrichtung bis ans rechte Ende.

1. Zwei Vergleiche sind nicht automatisch zwei vollständige Runden.
2. Bearbeite hier nur 0/1 und 1/2; Index 3 bleibt noch unverändert.

Nach dem Paar 0/1 steht [3, 4, 2, 1], nach dem Paar 1/2 [3, 2, 4, 1]. Das Paar 2/3 wurde noch nicht geprüft.

1. Ein Vergleich kann ohne Tausch enden.
2. Beide Nachbarpaare sind bereits geordnet, daher setzt kein Schritt das Flag auf True.

Weder 1 > 2 noch 2 > 3 trifft zu. Das Flag bleibt False; erst nach dem gesamten Durchlauf ist der Frühabbruch begründet.

1. Weil du auf j+1 zugreifst, darf j höchstens len(ergebnis)−2 sein.
2. Eine Schleife reicht für eine Runde; eine zweite äußere Schleife würde hier zu viel sortieren.

def bubble_runde(a):
    ergebnis = a.copy()
    for j in range(len(ergebnis) - 1):
        if ergebnis[j] > ergebnis[j + 1]:
            ergebnis[j], ergebnis[j + 1] = ergebnis[j + 1], ergebnis[j]
    return ergebnis

1. Setze getauscht zu Beginn jeder äußeren Runde auf False und nur bei wirklichem Tausch auf True.
2. Die Abbruchprüfung steht hinter der inneren Schleife. Sonst würde etwa [1, 4, 3, 2] zu früh enden.

def bubble_sort(a):
    ergebnis = a.copy()
    for ende in range(len(ergebnis) - 1, 0, -1):
        getauscht = False
        for j in range(ende):
            if ergebnis[j] > ergebnis[j + 1]:
                ergebnis[j], ergebnis[j + 1] = ergebnis[j + 1], ergebnis[j]
                getauscht = True
        if not getauscht:
            break
    return ergebnis

1. Erhöhe den Zähler innerhalb der Tauschbedingung, nicht bei jedem Schleifenschritt.
2. Eine bereits sortierte Liste hat 0 Tausche, obwohl Nachbarvergleiche stattfinden können.

def bubble_tauschzahl(a):
    arbeit = a.copy()
    anzahl = 0
    for ende in range(len(arbeit) - 1, 0, -1):
        for j in range(ende):
            if arbeit[j] > arbeit[j + 1]:
                arbeit[j], arbeit[j + 1] = arbeit[j + 1], arbeit[j]
                anzahl += 1
    return anzahl

1. Ein Tauschflag sammelt Informationen über eine ganze Runde.
2. Bei [1, 4, 3] ist das erste Paar geordnet, das zweite aber nicht.

Erst der vollständige tauschfreie Durchlauf bestätigt, dass alle Nachbarpaare des aktiven Bereichs geordnet sind. Ein einzelnes korrektes Paar sagt nichts über spätere Paare.

1. Gleiche markierte Datensätze könnten ihre Reihenfolge nur ändern, wenn sie aneinander vorbeitauschen.
2. Prüfe die Behauptung zum Minimum mit [3, 2, 1]: Nach einer Runde steht [2, 1, 3].

Strenges > lässt gleiche Schlüssel in ihrer Reihenfolge. Durch die Links-nach-rechts-Vergleiche wandert ein größter Wert ans Ende; das Minimum muss dagegen mehrere Runden nach links wandern.