Dein Fortschritt:
0 / 0 Aufgaben
1
Wer ist A, B und C?
AFB I–IIEine Informatik-AG hat Selectionsort, Insertionsort und Bubblesort mit Abbruch (Flag getauscht) implementiert und mit Zählvariablen versehen. Gezählt werden die Vergleiche V zweier Elemente und die Umstellungen U (Vertauschungen bzw. Verschiebungen; bei Selectionsort wird nur getauscht, wenn das Minimum nicht schon vorn steht). Die Reihungen haben jeweils n = 1000 Elemente. Leider wurden die Namen der Verfahren in der Messtabelle durch A, B und C ersetzt.
Messtabelle für n = 1000
| Verfahren | vorsortiert | zufällig | umgekehrt | |||
|---|---|---|---|---|---|---|
| V | U | V | U | V | U | |
| A | 999 | 0 | 498 324 | 241 475 | 499 500 | 499 500 |
| B | 499 500 | 0 | 499 500 | 995 | 499 500 | 500 |
| C | 999 | 0 | 242 469 | 241 475 | 499 500 | 499 500 |
- Beschreiben Sie neben der Anzahl der Vergleiche drei weitere Kriterien, nach denen Sortierverfahren verglichen werden.
- Ordnen Sie den Buchstaben A, B und C begründet die drei Verfahren zu.
- Berechnen Sie, wie viele Vergleiche Verfahren B bei n = 2000 benötigt, und begründen Sie, warum sich die Anzahl bei Verdopplung von n etwa vervierfacht.
- Erklären Sie, warum Verfahren B bei umgekehrt sortierter Eingabe nur 500 Umstellungen benötigt.
Hinweise
Hinweis zu Aufgabe a)
Denken Sie an Speicher, an Schreibzugriffe, an gleiche Werte und an die Eingabe.
Hinweis zu Aufgabe b)
Welches Verfahren vergleicht immer gleich oft? Die beiden übrigen unterscheiden sich nur in der Spalte „zufällig“.
Hinweis zu Aufgabe c)
\(V(n)=\frac{n(n-1)}{2}\); ausmultiplizieren und den Term mit \(n^2\) betrachten.
Hinweis zu Aufgabe d)
Verfolgen Sie die ersten Runden von Selectionsort bei 1000, 999, …, 1: Welche zwei Elemente werden getauscht?