Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:algorithmen:sorting:quicksort:start [27.02.2023 18:47] – [Teilen] Frank Schiebel | faecher:informatik:oberstufe:algorithmen:sorting:quicksort:start [03.03.2024 17:16] (aktuell) – [Vom Teilen zum Quicksort] Marco Kuemmel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Quicksort ====== | ====== Quicksort ====== | ||
- | Ein weiterer, sehr effizienter Algorithmus zum Sortieren großer Datenmengen ist Quicksort. Auch Quicksort findet sich in zahlreichen aktuellen Bibliotheksimplementationen moderner Programmiersprachen wieder. Quicksort wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von andren | + | Ein weiterer, sehr effizienter Algorithmus zum Sortieren großer Datenmengen ist Quicksort. Auch Quicksort findet sich in zahlreichen aktuellen Bibliotheksimplementationen moderner Programmiersprachen wieder. Quicksort wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von anderen |
===== Prinzip ===== | ===== Prinzip ===== | ||
- | * (Man vermischt das Array aus hat Performanzgründen) | + | * (Man vermischt das Array aus Performanzgründen) |
* Man wählt das erste Element((das wegen des Mischvorgangs jetzt zufällig ist)) als **Pivotelement** und ordnet anschließend alle Elemente so an, dass das Pivotelement das Array in **zwei Teile teilt**: Die Elemente des ersten Teilarrays sind alle kleiner als das Pivotelement, | * Man wählt das erste Element((das wegen des Mischvorgangs jetzt zufällig ist)) als **Pivotelement** und ordnet anschließend alle Elemente so an, dass das Pivotelement das Array in **zwei Teile teilt**: Die Elemente des ersten Teilarrays sind alle kleiner als das Pivotelement, | ||
* Anschließed verfährt man mit den Teilarrays rekursiv analog. | * Anschließed verfährt man mit den Teilarrays rekursiv analog. | ||
Zeile 21: | Zeile 21: | ||
=== (A1) === | === (A1) === | ||
- | Führe das Verfahren für beide Teilarrays von Hand erneut aus, ohne erneut zu mischen. Vollziehe für das orange Teilarray 3 weitere Teilungsvorgänge nach. Warum machen drei weitere Teilungen | + | Führe das Verfahren für beide Teilarrays von Hand erneut aus, ohne erneut zu mischen. Vollziehe für das orange Teilarray 3 weitere Teilungsvorgänge nach. Warum machen drei weitere Teilungen beim blauen Teilarray keinen Sinn? |
++++ Lösungshinweise | | ++++ Lösungshinweise | | ||
Zeile 37: | Zeile 37: | ||
===== Vom Teilen zum Quicksort ===== | ===== Vom Teilen zum Quicksort ===== | ||
+ | Verfügt man über eine funktionale " | ||
+ | |||
+ | < | ||
+ | funktion sort(a, li, re) | ||
+ | falls li < re dann | ||
+ | | ||
+ | | ||
+ | | ||
+ | ende | ||
+ | ende | ||
+ | </ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A3) === | ||
+ | |||
+ | Was ist der Basisfall bei diesem Rekursionsaufruf? | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
+ | |||
+ | Implementiere Quicksort in der Methode '' |