Bubblesort

Der Bubblesort ist einer der einfachsten Sortieralgorithmen. Die Vorsortierung der zu sortierenden Datenmenge hat keinerlei Auswirkung auf die Laufzeit.

Laufzeit

Selbst nach der Optimierung des Algorithmus werden viele Einträge doppelt verglichen. Im Allgemeinen beträgt die Laufzeit Θ(n²), kann jedoch durch Optimierungen auf O(n²) reduziert werden.

Einsatzgebiet

Aufgrund der Einfachheit und der schlechten performance gibt es keine besonderen Einsatzgebiete. Jedoch für “proof of concept” Projekte schnell und einfach implementiert.

Sortierung

Jedes Element der Sammlung wird mit jedem anderen Element verglichen und bei Bedarf, je nach Sortierkriterium, vertauscht. In der folgenden grafischen Veranschaulichung wird eine Sammlung von Integern sortiert.

Folgende Liste möchten wir sortieren.

List

 

 

Für den Vergleich (Eintrag für Eintrag) werden 2 ineinander verschachtelte Schleifen benötigt. Farblich jeweils durch Blau und Gelb markiert.

1-3

Beide Iterationen beginnen bei dem Index 0. Da der Vergleich desselben Eintrages von Sinn befreit ist, wird bei Übereinstimmung beider Schleifenzeiger der Eintrag übersprungen.

  1. Iteration: Schleife1 zeigt auf Index 0 (Wert 3). Schleife 2 zeigt auf Index 1 (Wert 1). 3 > 1 und somit werden die beide vertauscht.
  2. Iteration: Schleife 1 zeigt auf Index 0 (Wert 1). Schleife 2 zeigt auf Index 2 (Wert 9). 1 < 9. Kein Tausch nötig.

 

4-64. Iteration: Der Zeiger der ersten Schleife wird inkrementiert und der Zeiger der zweiten Schleife auf 0 zurückgesetzt. Nun beginnt das Spiel erneut…

 

 

 

 

 

7-9

 

 

 

 

 

 

 

Umsetzung(C#)

One Comment

  1. Pingback: Combosort | Indie Dev

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.