Stability

In dieser Lektion werden wir die Stabilität des Bubble-Sort-Algorithmus überprüfen.

Was ist Stabilität?

Ein Sortieralgorithmus wird als stabil bezeichnet, wenn zwei Objekte mit gleichen Schlüsseln in der sortierten Ausgabe in derselben Reihenfolge erscheinen, wie sie im zu sortierenden Eingabearray erscheinen.

Wenn wir zum Beispiel das Array [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] sortieren müssen, haben wir hier zwei Achten, bezeichnet als 8₁ und 8₂. Nach dem Sortieren können zwei mögliche Arrays erhalten werden – [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] und [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]. Beide Arrays sind sortiert, aber im zweiten ist die Reihenfolge der beiden Achten anders, während sie im ersten Array dieselbe ist wie im Eingabearray.

Lassen Sie uns dies nun für den Bubble-Sort-Algorithmus überprüfen.

Erster Durchlauf: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

Zweiter Durchlauf: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Nach allen Durchläufen wird die endgültige Ausgabe sein: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Beachten Sie, dass die Reihenfolge der Achten sowohl im Ausgabe- als auch im Eingabearray gleich ist.

Daher ist der Bubble-Sort-Algorithmus stabil!