Selectionsort: Übungen – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Ü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.

Was passt nicht?

AFB I

Nennen Sie in jeder der drei Gruppen die Karte, die nicht zu Selectionsort passt, und klicken Sie diese an.

In jeder Gruppe passt genau eine Karte nicht zu den anderen. Klicken Sie dieses „Kuckucksei“ an und prüfen Sie dann. Mit der Tastatur: Tab zur Gruppe, ←/→ wandern, Enter wählt.

Eine Aussage über Selectionsort stimmt nicht

Zwischenstände von {6, 2, 9, 4, 1}

Eine Zeile gehört nicht in selectionSort

In jeder Gruppe stimmen drei Karten überein, eine weicht ab: eine falsche Eigenschaft, ein unmöglicher Zwischenstand und eine fremde Codezeile.

Prüfen Sie in jeder Gruppe, was die vier Karten gemeinsam haben, und suchen Sie die Abweichung.

Gruppe 2: Spielen Sie die ersten Runden durch und vergleichen Sie. Gruppe 3: Selectionsort tauscht nie mit dem Nachbarn, sondern mit dem Minimum.

Wann lohnt sich Sortieren?

AFB IIMix

Ein Verzeichnis mit \(n\) Einträgen wird \(k\)-mal durchsucht. Variante A: \(k\)-mal lineare Suche, höchstens \(n\) Vergleiche je Suche. Variante B: einmal mit Selectionsort sortieren, danach \(k\)-mal binär suchen, höchstens \(b = \lfloor\log_2 n\rfloor + 1\) Vergleiche je Suche. Leiten Sie her, ab wie vielen Suchen \(k\) die Variante B im ungünstigsten Fall weniger Vergleiche braucht: Ordnen Sie jeder Zeile die passende Begründung zu. Zwei Karten bleiben übrig.

Ordnen Sie jeder Zeile der Herleitung die passende Begründung zu: Karte anklicken, dann das Feld neben der Zeile (oder Karte direkt auf das Feld ziehen). Mit der Tastatur: Tab zur Karte, Enter, dann Tab zum Feld und Enter. Ein Klick auf ein belegtes Feld legt die Karte zurück. Nicht alle Karten werden gebraucht.

Zu zeigen: Sortieren und binär suchen lohnt sich im ungünstigsten Fall ab k > n(n − 1) / (2 · (n − b)) Suchen.

k · n > n(n − 1)/2 + k · b
k · n − k · b > n(n − 1)/2
k · (n − b) > n(n − 1)/2
k > n(n − 1) / (2 · (n − b))

Für n = 1 000 ist b = 10. Dann gilt k > 1 000 · 999 / (2 · 990) ≈ 504,5, die Variante B lohnt sich also ab 505 Suchen: 499 500 + 505 · 10 = 504 550 Vergleiche gegen 505 000. Bei 504 Suchen gewinnt noch die lineare Suche (504 540 gegen 504 000).

Stellen Sie die Gesamtkosten beider Varianten einander gegenüber und lösen Sie nach k auf. Das Sortieren fällt nur einmal an.

Bringen Sie alle Terme mit k auf eine Seite und klammern Sie k aus. Geteilt wird durch n − b, eine positive Zahl: Das Zeichen bleibt.

Runde für Runde auswählen

AFB I

Ein Quiz speichert die Punktzahlen punkte = {31, 8, 54, 19, 42, 5}. Wenden Sie Selectionsort (aufsteigend) auf diese Reihung an.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

Minimum in Runde 1:

In Runde 1 werden die Indizes getauscht:

Reihung nach Runde 2:

Reihung nach Runde 3:

Echte Vertauschungen insgesamt:

Runde 1 tauscht 31 und 5 → 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.

Ansatz: Markieren Sie nach jeder Runde den sortierten Teil mit einem Strich; gesucht wird nur rechts davon.

Weiter: Getauscht wird immer mit dem ersten Element des unsortierten Teils, also mit Index 0, 1, 2, …