Übungsaufgaben
Zehn Übungen zu Bubblesort — vom einzelnen Durchlauf über Code und Zählen bis zu Varianten. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
Nennen Sie zu jeder Aussage über Bubblesort (aufsteigend sortieren), ob sie stimmt.
Ein Kiosk speichert die Verkaufszahlen einer Woche in verkauf = {6, 11, 2, 9, 4}. Stellen Sie den ersten Durchlauf von Bubblesort als Tracetabelle dar: Belegung der Reihung nach dem Vergleich von verkauf[j] und verkauf[j + 1].
| j | [0] | [1] | [2] | [3] | [4] | Tausch? |
|---|---|---|---|---|---|---|
| 0 | 6 | 11 | 2 | 9 | 4 | nein |
| 1 | ||||||
| 2 | ||||||
| 3 |
6 2 9 4 11. Die 2 ist dagegen nur einen Platz nach links gerutscht — für sie braucht es noch weitere Durchläufe.Geben Sie die fehlenden Bausteine der Java-Methode an, die die int-Reihung a aufsteigend und stabil sortiert.
for (int i = 0; i < a.length ; i++) {
for (int j = 0; j < a.length - 1 ; j++) {
if (a[j] a[j + 1]) {
int hilf = ;
a[j] = a[j + 1];
a[j + 1] = ;
} } }
>= würde auch sortieren, tauscht aber gleiche Werte unnötig — Bubblesort wäre dann nicht mehr stabil. a[j + 1] als Startwert von hilf würde den Wert von a[j] verlieren.a[j + 1], einen wegen der schon fertigen Elemente rechts.a[j] in hilf retten, dann überschreiben.Beim Sortieren der Punktzahlen eines Quiz wurde die Reihung vor dem Sortieren und nach jedem Durchlauf notiert — die Zettel sind durcheinandergeraten. Bestimmen Sie die Reihenfolge vom Start bis zur sortierten Reihung.
4 8 6 2 9 3
4 6 2 8 3 9
4 2 6 3 8 9
2 4 3 6 8 9
2 3 4 6 8 9
9, dann 8 9, dann 6 8 9. Die 2 wandert pro Durchlauf genau einen Platz nach links — genau daran erkennt man die Reihenfolge der mittleren Zeilen.Eine Schulbibliothek sortiert die Ausleihzahlen ihrer Bücher mit der Grundversion von Bubblesort. Berechnen Sie die Anzahl der Vergleiche.
- Vergleiche im 1. Durchlauf bei n = 8 Vergleiche
- Vergleiche im 5. Durchlauf bei n = 8 Vergleiche
- Vergleiche insgesamt bei n = 8 Vergleiche
- Vergleiche insgesamt bei n = 80 Vergleiche
Ein Schüler hat Bubblesort für die Reihung h der Sprunghöhen beim Hochsprung programmiert. Überprüfen Sie jede Zeile und korrigieren Sie die fehlerhaften.
j = h.length - 1 greift h[j + 1] hinter das Ende — ArrayIndexOutOfBoundsException; richtig ist j < h.length - 1 - i. Zeile 6: Der gerettete Wert gehört nach h[j + 1]; sonst steht nach dem „Tausch“ zweimal derselbe Wert in der Reihung.hilf geschrieben wird.Die Reihung {8, 5, 3, 9, 1} wurde mit drei verschiedenen Verfahren aufsteigend sortiert. Ordnen Sie jedem Zwischenstand Verfahren und Zeitpunkt zu.
Die Reihung {20, 30, 40, 50, 60, 70, 80, 10} ist „fast sortiert“: Nur ein Element steht falsch. Sie wird mit bubbleSortMitAbbruch (Flag getauscht) sortiert. Ermitteln Sie die Anzahl der Vergleiche.
true, und es wird nie vorzeitig abgebrochen: \(7+6+\dots+1=28\) Vergleiche — genauso viele wie in der Grundversion. Stünde dagegen die 80 vorn ({80, 10, 20, …, 70}), wären es nur \(7+6=13\).An der Grundversion bubbleSort wird jeweils genau eine Stelle geändert. Beurteilen Sie, bei welchen Änderungen jede int-Reihung weiterhin korrekt aufsteigend sortiert wird.
- i werden nur schon fertige Paare zusätzlich verglichen — mehr Arbeit, aber richtig. Mit >= wird weiterhin sortiert, allerdings nicht mehr stabil. Ein zusätzlicher Durchlauf schadet nicht (seine innere Schleife läuft gar nicht). Mit a.length - 2 fehlt der letzte Durchlauf ({3, 2, 1} wird zu {2, 1, 3}), a.length - i löst eine ArrayIndexOutOfBoundsException aus, und < sortiert absteigend.{3, 2, 1}.Bubblesort soll so verändert werden, dass jeder Durchlauf von rechts nach links läuft und das kleinste Element nach vorn bringt. Dabei sollen nur die noch unsortierten Paare verglichen werden, und das Verfahren soll stabil bleiben.
for (int i = 0; i < a.length - 1; i++) {
for (int j = ; j > ; j--) {
if () { tausche a[j - 1] und a[j] }
Nach Durchlauf k stehen fest:
j von a.length - 1 abwärts bis i + 1, werden genau die Paare (j − 1, j) im unsortierten Teil ab Index i geprüft — \(n-1-i\) Vergleiche wie bisher. Mit a[j - 1] > a[j] wird das kleinere Element mitgenommen und „sinkt“ nach links. >= wäre nicht stabil, j > 0 würde fertige Paare erneut vergleichen, j > i + 1 das Paar an Index i vergessen.(i, i + 1) — also ist der kleinste Wert von j gleich i + 1.