Dreißig Übungen zu Selectionsort: Runden, Tracetabellen, Code und Aufwand — von AFB I bis AFB III.
Ihr Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.
A1
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.
AEine Aussage über Selectionsort stimmt nicht
BZwischenstände von {6, 2, 9, 4, 1}
CEine 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.
A2
Aufwand bei n = 16
AFB II
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.
Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Lineare Suche prüft ohne Treffer alle 16 Elemente, binäre Suche halbiert: 16 → 8 → 4 → 2 → 1, also höchstens 5 Durchläufe. Das Minimum braucht \(n-1=15\) Vergleiche — genau Runde 1 von Selectionsort. Runde 3 vergleicht noch mit \(16-3=13\) Elementen, die ganze Sortierung kostet \(\frac{16\cdot15}{2}=120\).
Ansatz: Die Minimumsuche ist eine lineare Suche ohne Abbruch: ein Vergleich pro weiteres Element.
Weiter: In Runde \(k\) sind noch \(n-k+1\) Elemente unsortiert, also \(n-k\) Vergleiche.
A3
Wann passt Selectionsort?
AFB II
Ordnen Sie jede Anforderung ein: Passt Selectionsort wegen seiner Eigenschaften (Zahl der Vergleiche, Zahl der Vertauschungen, in-place, Stabilität) gut dazu oder schlecht?
Wischen Sie die oberste Karte nach links (passt gut) oder nach rechts (passt schlecht) – mit Maus oder Finger ziehen oder die Knöpfe nutzen. Tastatur: Fokus auf die Karte, ←/→. Ein Klick auf eine abgelegte Karte holt sie zurück. Ist der Stapel leer, prüfen Sie.
Selectionsort tauscht höchstens n − 1 mal und braucht keine zweite Reihung, das passt zu teuren Tauschvorgängen und zu knappem Speicher. Er ist aber nicht stabil, vergleicht immer n(n − 1)/2 mal – auch bei fast sortierten Daten – und wächst für zehn Millionen Einträge quadratisch.
Fragen Sie bei jeder Karte: Welche Eigenschaft von Selectionsort ist hier gefragt – Tauschen, Vergleichen, Speicher oder Reihenfolge gleicher Werte?
Wenige Vertauschungen und kein Zusatzspeicher sprechen für Selectionsort; die feste Vergleichszahl und die fehlende Stabilität sprechen dagegen.
