Arbeitsblatt: Quicksort (Arbeitsblatt)

Informatik – Grundkurs 11 Quicksort I. Die Idee des Algorithmus „Quicksort Aufgabe 1 Das Zahlenfeld 42 73 62 15 24 105 38 97 78 18 75 99 80 58 6 56 soll wie folgt sortiert werden: Alle Zahlen, die kleiner oder gleich dem Trennwert 60 sind, landen in Feld A1, alle Zahlen die größer sind als der Trennwert 60 landen in Feld A2. A1 {x x 60} 60 Aufgabe 2 Sortiere weiter! II. Sortieren mit Quicksort Aufgabe 1 Sortiere die beiden Zahlenfelder nach „Quicksort, wie es in Teil vorgemacht wurde (Aufrufbaum). Einen geeigneten Trennwert musst du jeweils selbst bestimmen. a) b) 33 48 40 43 87 7 56 54 15 40 7 23 12 56 34 1 1 17 91 99 39 10 87 52 5 11 86 20 31 2 99 4 39 Informatik – Grundkurs 11 Quicksort Aufgabe 2 a) Der Aufrufbaum aus Teil hat eine Höhe von 4 Zeilen. Vergleiche die Höhe mit den von dir gezeichneten Bäumen aus Aufgabe 1 (a) und (b). b) Wie hoch wäre (minimal – im besten Fall) ein Aufrufbaum mit 20 zu sortierenden Elementen.(100, 500, 1000, 10000, 100000 Elementen)? c) Welcher mathematische Zusammenhang besteht hier? III Das Programm 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. procedure quicksort (l, : integer); var i, : integer; trennwert hilf integer; begin : l; : r; trennwert : a[(lr) div 2]; repeat while a[i] trennwert do : 1; while trennwert a[j] do : j-1; if j; if then quicksort (l, j); if then quicksort (i, r); end; Aufgabe 5 a) Stelle die Zeilen 4 – 28 als Struktogramm dar! b) Erkläre mit eigenen Worten, was in den inneren Schleifen passiert. c) Erkläre mit eigenen Worten, was in der äußeren Schleife passiert. Aufgabe 6 Bei einer Feldgröße von 1n wird die Prozedur Quicksort wie folgt aufgerufen: procedure TForm1.Button1Click(Sender: TObject); begin unit1.quicksort(1,n); end; Implementieren Sie das Programm! Aufgabe 7 Greifen Sie die Laufzeit ab (das ist bekannt!!!) und überprüfen Sie, ob Quicksort ein Laufzeitverhalten von O(n) haben kann. 2