Bubblesort
Prinzip: Die größte Zahl im unsortierten Teil des Array wandert nach hinten. Das wird so lange wiederholt, bis das Array sortiert ist. Die großen Zahlen steigen wie Blasen im Zahlenmeer nach oben.
Durchführung: Die ersten beiden Zahlen des Array werden miteinander verglichen. Ist die Erste größer als die Zweite, werden sie vertausch. Danach werden die zweite und die dritte Zahl verglichen und eventuell vertauscht.
| |
|
|
|
|
|
Schritt |
| 3 |
7 |
5 |
1 |
3 |
2 |
1 |
| 3 |
7 |
5 |
1 |
3 |
2 |
2 |
| 3 |
5 |
7 |
1 |
3 |
2 |
3 |
| 3 |
5 |
1 |
7 |
3 |
2 |
4 |
| 3 |
5 |
1 |
3 |
7 |
2 |
5 |
| 3 |
5 |
1 |
3 |
2 |
7 |
|
Für das Durchlaufen der Zahlenreihe sind bei 6 Elementen insgesamt 5 Schritte notwendig, um die größte Zahl (hier die 7) ans Ende zu schieben.
Aufgabe: Verwende das erste Sortierprogramm als Grundlage.
- Erzeuge im Array 10 Zufallszahlen zwischen 1 und 20.
- Zeige das unsortierte Array.
- Rufe eine Funktion bubble(zahlen) auf. Der übergebene Parameter zahlen ist das ungeordnete Array.
- In der Funktion soll die größter Zahl im Array nach hinten geschoben werden. Mehr nicht!
Dazu kann eine for-Schleife verwendet werden.
- Die Funktion gibt das Array zurück.
- Die aufrufende Funktion gibt das Array aus.
Aufgabe: In einer weiteren Schleife, die die innere Schleife umschließt, wird die erste Schleife genau so oft aufgerufen, wie das Array Elemente hat. Das ist zwar uneffektiv, jedoch einfach zu programmieren und funktioniert.
Optimierung
Optimierung bedeutet, dass durch geeignete Maßnahmen das Sortierverfahren schneller wird.
- Baue in das Programm die Zeitmessug wieder ein
- Erhöhe die Anzahl der Zahlen im Array so, dass die Sortierzeit einige Sekunden dauert.
- Verändere die inneres Schleife so, dass sie bei jedem Aufruf durch die äußere Schleife um einen Durchlauf weniger wird. Die Sortierzeit sollte sich dadurch deutlich verringern.
- Wenn bei einem Durchlauf keine Vertauschung mehr notwenig war, kann das Verfahren abgebrochen werden. Überprüfe, ob das eine weitere Verringerung der Zeit bringt.
- Informiere dich über das Bubblesort-Verfahren in der Wikipedia. Informiere dich weiterhin über Cocktailsort und versuche, diesen Algorithmus umzusetzen.
zurück