|
BubbleSort gebührt zwar die Ehre, eines der
ersten Sortierverfahren der Informatik gewesen zu sein, aber es leidet
unter dem 'unintelligenten' Algorithmus, der alle Elemente systematisch
vergleicht, selbst in dem pathologischen Fall einer bereits sortierten
Liste.
procedure TWortListe.Bubblesort1;
(* ------------------------------------------------------------------ *)
(* Auftrag: lineares Sortieren durch systematisches Vergleichen aller *)
(* Elemente und
Tauschen mit dem nachfolgenden
Element *)
(* Vorher : Liste ist nicht
leer
*)
(* Nachher: Liste ist aufsteigend
sortiert
*)
(* ------------------------------------------------------------------ *)
| 17 |
36 |
24 |
12 |
10 |
98 |
| 17 |
24 |
12 |
10 |
36 |
98 |
| 17 |
12 |
10 |
24 |
36 |
98 |
| 12 |
10 |
17 |
24 |
36 |
98 |
| 10 |
12 |
17 |
24 |
36 |
98 |
Die hohen Werte steigen nach einander 'like bubbles' nach oben.
Zur Steigerung der Effizienz lässt sich BubbleSort noch in
zwei Schritten optimieren.
1. Optimierung
| 17 |
36 |
24 |
12 |
10 |
98 |
| 17 |
24 |
12 |
10 |
36 |
98 |
| 17 |
12 |
10 |
24 |
36 |
98 |
| 12 |
10 |
17 |
24 |
36 |
98 |
| 10 |
12 |
17 |
24 |
36 |
98 |
Der Teil der Liste, der bereits hinten sortiert ist, wird bei
jedem neuen Durchlauf nicht mehr verglichen.
procedure TWortListe.Bubblesort2;
(* ----------------------------------------------------------------- *)
(* Auftrag: lineares Sortieren durch Vertauschen des
nachfolgenden *)
(* Elements im
Restfeld, das von hinten verkleinert wird. *)
(* Vorher : Liste ist nicht
leer
*)
(* Nachher: Liste ist aufsteigend
sortiert
*)
(* ----------------------------------------------------------------- *)
2. Optimierung
Das Vergleichen der
Elemente wird wieder holt bis kein Tauschvorgang mehr stattgefunden
hat. Dabei wird wie in BubbleSort2 das Restfeld verkleinert.
procedure TWortListe.Bubblesort3;
(* ----------------------------------------------------------------- *)
(* Auftrag: lineares Sortieren durch Vergleichen und Vertauschen des *)
(* nachfolgenden
Elements bis nicht mehr getauscht wird. *)
(* Endmarke
rueckt vor und verkleinert
Restfeld
*)
(* vorher : Liste ist nicht
leer
*)
(* nachher: Liste ist aufsteigend
sortiert
*)
(* ----------------------------------------------------------------- *)
Aufgabe:
Implementieren Sie die zwei Methoden und berechnen Sie wie
viele Vergleiche stattfinden!
|
