Bubblesort Referat

Infos zum Sortierverfahren Bubblesort (Handout zum Referat) folgt:

Gliederung:

1. Einleitung

2. Prinzip

3. Analyse

3.1. Schlimmster Fall4. Beispiel

3.2. Bester Fall

3.3. Durchschnittlicher Fall

3.4. Hasen und Schildkröten

4. Beispiel

1. Einleitung

– einfacher, stabiler Sortieralgorithmus

– für größere Datenmengen nicht geeignet

2. Prinzip

– vergleicht der Reihe nach zwei benachbarte Elemente

– diese werden vertauscht, falls falsche Reihenfolge vorliegt

– mehrere Durchläufe nötig

3. Analyse3.1. Schlimmster Fall

– Bubblesort hat schlechtmöglichste Laufzeit (n – 1)2 für Listen der Länge n

– pro Durchlauf kann nur ein Element bewegt werden

– Komplexität im schlimmsten Fall bei (n – 1)2

3.2. Bester Fall

– Liste ist bereits sortiert

– Elemente bereits nah an den Stellen, an die sie sortiert werden sollen

– Laufzeit erheblich besser als (n – 1)2

3.3. Durchschnittlicher Fall

– die allgemein erwartete Laufzeit des Verfahren beträgt ((n – 1)2 /2)

3.4. Hasen und Schildkröten

– Position der Elemente maßgeblich für Sortieraufwand

– große Elemente am Anfang werden relativ schnell nach unten getauscht

– kleine Elemente am Ende bewegen sich eher langsam nach oben

4. Beispiel BUBBLESORT

1. Durchlauf

55 07 78 12 42

07 55 78 12 42

07 55 78 12 42

07 55 12 78 42

2. Durchlauf

07 55 12 42 78

07 55 12 42 78

07 12 55 42 78

3. Durchlauf

07 12 42 55 78

07 12 42 55 78

4. Durchlauf

07 12 42 55 78

07 12 42 55 78

Fertig sortiert!