Übungsaufgaben
Zehn Übungen zum Auswählen, Zählen und Korrigieren — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
Ein Quiz speichert die Punktzahlen punkte = {31, 8, 54, 19, 42, 5}. Wenden Sie Selectionsort (aufsteigend) auf diese Reihung an.
Minimum in Runde 1:
In Runde 1 werden die Indizes getauscht:
Reihung nach Runde 2:
Reihung nach Runde 3:
Echte Vertauschungen insgesamt:
5 8 54 19 42 31. In Runde 2 steht 8 schon vorn: kein Tausch. Runde 3 tauscht 54 und 19, Runde 4 tauscht 54 und 31, Runde 5 findet 42 schon an seinem Platz. Also 3 echte Vertauschungen bei 5 Runden. Häufiger Fehler: in Runde 3 wird 19 mit dem Nachbarn getauscht statt mit dem ersten Element des unsortierten Teils.Geben Sie zu jeder Aussage über Selectionsort, ob sie stimmt.
Die Methode soll die Reihung a mit Selectionsort aufsteigend sortieren. Ordnen Sie jeder Lücke den passenden Baustein zu — zwei Bausteine bleiben übrig.
for (int i = 0; i < a.length - 1; i++) { int minPos = ; for (int j = ; j < a.length; j++) if (a[j] < ) minPos = j; int hilf = ; a[i] = a[minPos]; a[minPos] = ;}
minPos = 0 würde jede Runde wieder im schon sortierten Teil anfangen. a[j] in der Bedingung vergliche das Element mit sich selbst. Der Tausch braucht die Hilfsvariable, weil a[i] in der Zeile davor schon überschrieben wird.a[i], bevor er überschrieben wird — er kommt am Ende nach a[minPos].Ein Fahrradladen sortiert Rahmenhöhen in cm: rahmen = {47, 18, 90, 26, 13}. Stellen Sie den Ablauf von Selectionsort in der Tracetabelle dar: Position des Minimums und Reihung nach jeder Runde.
1 2 3 4 5. Enter prüft ebenfalls.| Runde | i | minPos | rahmen danach |
|---|---|---|---|
| 1 | 0 | ||
| 2 | 1 | ||
| 3 | 2 | ||
| 4 | 3 |
minPos = i, keine Änderung). In Runde 4 ist 47 an Index 4 kleiner als 90 an Index 3 — dieser letzte Tausch sortiert die beiden größten Werte. Insgesamt 10 Vergleiche und 3 echte Vertauschungen.minPos ist ein Index, kein Wert. Suchen Sie das Minimum immer nur ab Index i.13 18 90 26 47.Lina hat Selectionsort für die Reihung z programmiert, doch die Ausgabe ist falsch sortiert. Überprüfen Sie jede Zeile und korrigieren Sie die fehlerhaften.
z[i] statt mit dem bisher besten Kandidaten — dann gewinnt nicht das Minimum, sondern das letzte Element kleiner als z[i]. Zeile 8 schreibt den schon überschriebenen Wert zurück, statt hilf zu benutzen.z = {3, 1, 2}: Welche Zeile liefert zuerst etwas Unerwartetes?minPos, die Vergleichsbedingung und die letzte Zuweisung.Eine sortierte bzw. unsortierte Reihung hat \(n=16\) Elemente. Vergleichen Sie den Aufwand der Verfahren und verbinden Sie jedes mit der Anzahl der Vergleiche bzw. Durchläufe.
Der Aufwand von Selectionsort wird für Reihungen gleicher Länge \(n\), aber verschiedener Anordnung gemessen. Analysieren Sie für jede Größe (bezogen auf Struktogramm und Java-Methode der Inhaltsseite), wovon sie abhängt.
| Größe | hängt nur von n ab | hängt auch von der Anordnung ab |
|---|---|---|
| Anzahl der Vergleiche | ||
| Anzahl der echten Vertauschungen (Element wechselt den Platz) | ||
| Anzahl der Durchläufe der äußeren Schleife | ||
| Wie oft minPos ← j ausgeführt wird | ||
| Wie oft hilf ← a[i] ausgeführt wird |
minPos ← j steht im Ja-Zweig — und ob ein Element wirklich den Platz wechselt, hängt davon ab, wo das Minimum liegt.Ein Messgerät sortiert 1000 Messwerte mit Selectionsort in 0,5 s. Die Laufzeit ist proportional zur Anzahl der Vergleiche. Schätzen Sie die Laufzeit für größere Datenmengen ab.
- Vergleiche für n = 1000
- Vergleiche für n = 2000
- Faktor, um den die Vergleiche wachsen (eine Nachkommastelle)
- erwartete Laufzeit für 2000 Werte in s
- erwartete Laufzeit für 10 000 Werte in s
Eine Quiz-App sortiert die Liste (Ida, 3) (Jan, 2) (Kim, 3) (Leo, 1) mit Selectionsort aufsteigend nach der Anzahl der Fehler (Vergleich mit < nur auf die Fehlerzahl). Bestimmen Sie die Reihenfolge nach dem Sortieren.
Leo Jan Kim Ida. Runde 2 und 3 tauschen nichts, weil Ida (3) nicht kleiner als Kim (3) ist. Ida stand am Anfang vor Kim, jetzt dahinter — der weite Tausch in Runde 1 hat die Reihenfolge gleicher Werte verändert. Selectionsort ist nicht stabil.Die Reihung {2, 5, 9, 14, 20, 27, 35, 44, 54, 65} ist bereits aufsteigend sortiert. Berechnen Sie, wie viele Vergleiche Selectionsort trotzdem durchführt.