Dein Fortschritt:
0 / 0 Aufgaben
1
Die Messreihe
14 BEAFB I–IIIm Informatikkurs wurden drei Sortierverfahren mit einem Zähler für Vergleiche ausgestattet. Verfahren A erhielt zufällige Daten, Verfahren B ebenfalls zufällige Daten, Verfahren C bereits aufsteigend sortierte Daten. Die Namen der Verfahren wurden in der Tabelle weggelassen; es handelt sich um Selectionsort, Insertionsort und Mergesort.
Gezählte Vergleiche der drei Verfahren
| n | Verfahren A | Verfahren B | Verfahren C |
|---|---|---|---|
| 1 000 | 499 500 | 8 732 | 999 |
| 2 000 | 1 999 000 | 19 443 | 1 999 |
| 4 000 | 7 998 000 | 42 850 | 3 999 |
- Ermitteln Sie für jedes Verfahren, um welchen Faktor die Zahl der Vergleiche bei Verdopplung von \(n\) wächst. (3 BE)
- Ordnen Sie den Verfahren A, B und C die Namen Selectionsort, Insertionsort und Mergesort zu und begründen Sie jede Zuordnung. (4 BE)
- Schätzen Sie für alle drei Verfahren die Zahl der Vergleiche bei \(n = 1\,000\,000\) ab und geben Sie die Rechenzeit bei \(10^9\) Vergleichen pro Sekunde an. (4 BE)
- Nennen Sie zwei weitere Kriterien außer der Zahl der Vergleiche, nach denen die Verfahren beurteilt werden sollten, und ordnen Sie Mergesort danach ein. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Teilen Sie jeweils den Wert bei \(2n\) durch den Wert bei \(n\).
Hinweis zu Aufgabe b)
Faktor 4 spricht für \(n^2\), Faktor 2 für \(n\), etwas mehr als 2 für \(n\log_2 n\). Beachten Sie auch, welche Daten C bekam.
Hinweis zu Aufgabe c)
Verwenden Sie die Formeln \(\frac{n(n-1)}{2}\), \(n\log_2 n\) und \(n - 1\).
Hinweis zu Aufgabe d)
Denken Sie an Speicher, Aufrufstapel und gleiche Schlüssel.