Übungsaufgaben
Zehn Übungen zum Vergleich von Selectionsort, Insertionsort und Bubblesort — von Eigenschaften über Messwerte bis zur Wahl des passenden Verfahrens. Wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
Ordnen Sie jede Eigenschaft dem Sortierverfahren zu, auf das sie (als einziges der drei) zutrifft.
Nennen Sie zu jeder Aussage über die Vergleichskriterien, ob sie stimmt.
Eine Reihung enthält die Zahlen 1 bis 10 — einmal aufsteigend, einmal absteigend sortiert. Geben Sie für jedes Verfahren die Anzahl der Vergleiche (V) und der Umstellungen (U) an. Bei Selectionsort zählt ein Tausch nur, wenn das Minimum nicht schon vorn steht.
| Eingabe | Selectionsort | Insertionsort | Bubblesort (Abbruch) | |||
|---|---|---|---|---|---|---|
| V | U | V | U | V | U | |
| vorsortiert | ||||||
| umgekehrt | ||||||
Ein Online-Shop sortiert 2 000 Bestellungen mit Bubblesort; im ungünstigsten Fall dauert das 0,8 s. Schätzen Sie, wie lange das Sortieren bei mehr Bestellungen im ungünstigsten Fall etwa dauert.
- Vergleiche bei n = 2 000 im ungünstigsten Fall Vergleiche
- geschätzte Zeit für n = 4 000 s
- geschätzte Zeit für n = 8 000 s
- geschätzte Zeit für n = 20 000 s
Die Reihung {2, 1, 4, 3, 6, 5, 8, 7} soll aufsteigend sortiert werden. Vergleichen Sie die Verfahren nach der Anzahl der Vergleiche — von wenigen zu vielen.
An einer Flussmessstelle liegen 50 Pegelwerte vor, die bereits aufsteigend sortiert sind. Sie werden trotzdem noch einmal mit Selectionsort sortiert. Berechnen Sie die Anzahl der Vergleiche.
Aus einem Referat über Sortierverfahren stammen die folgenden sechs Sätze. Überprüfen Sie jeden Satz und markieren Sie die falschen.
Ein Messstand hat für ein unbekanntes Verfahren X mit zufälligen Eingaben gemessen: n = 100: 4 950 Vergleiche, 97 Umstellungen; n = 200: 19 900 Vergleiche, 196 Umstellungen; n = 400: 79 800 Vergleiche, 395 Umstellungen. Beurteilen Sie, welche Schlussfolgerungen aus diesen Messwerten berechtigt sind.
In einer unsortierten Reihung mit 1 000 Artikelnummern wird häufig gesucht. Die lineare Suche braucht im ungünstigsten Fall 1 000 Vergleiche. Alternativ sortiert man einmal mit Insertionsort (ungünstigster Fall) und sucht danach binär mit höchstens 10 Vergleichen. Ermitteln Sie, ab wie vielen Suchvorgängen die zweite Variante im ungünstigsten Fall insgesamt weniger Vergleiche braucht.
Entscheiden Sie sich für jeden Anwendungsfall begründet für das geeignetste Verfahren.
Eine sortierte Bestenliste bekommt einen neuen Eintrag hinten angehängt und wird neu sortiert; wie gut er ist, weiß man vorher nicht.
Die Daten liegen auf einem Speicher, der sich bei jedem Schreibzugriff abnutzt.
Eine nach Namen sortierte Schülerliste soll nach Klassen sortiert werden; innerhalb einer Klasse soll die Namensreihenfolge bleiben, und es soll wenig geschrieben werden.
Die Eingabe ist umgekehrt sortiert, und es kommt nur auf die Zahl der Vergleiche an.