Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [31.01.2022 16:17] – [Arrays mit zwei oder mehr Elementen] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [24.01.2024 16:33] – [Quicksort] Marco Kuemmel
@@ Zeile 5: / Zeile 5: @@
 </WRAP>
-Quicksort ist ein sehr schnellet Sortieralgorithmus. Er kommt in der Praxis
+Quicksort ist ein sehr schneller Sortieralgorithmus. Er kommt in der Praxis
-häuﬁg zum Einsatz. Zahlreiche Standardbibliotheken verschiedener Programmiersprachen enthalten Methoden um zum Beispiel Arrays zu sortieren, die in als Quicksort implementiert sind. Zum Beispiel hat die  Standardbibliothek der Programmiersprache C eine Funktion namens
+häufig zum Einsatz. Zahlreiche Standardbibliotheken verschiedener Programmiersprachen enthalten Methoden, um zum Beispiel Arrays zu sortieren, die in als Quicksort implementiert sind. Zum Beispiel hat die  Standardbibliothek der Programmiersprache C eine Funktion namens
 ''qsort''. Quicksort verwendet ein [[..:..:teile_und_herrsche:start|Teile-und-herrsche-Prinzip]].
@@ Zeile 47: / Zeile 47: @@
 ===== Quicksort =====
-==== Leere Arrays und solche mit nur einem Element ====
+==== Leere Arrays, Arrays mit einem oder zwei Element ====
 Wir legen den Basisfall zugrunde: Wenn unser Array leer ist oder nur ein Element hat, ist es sortiert und kann direkt als sortiertes Array zurückgegeben werden:
@@ Zeile 79: / Zeile 79: @@
 {{:aufgabe.png?nolink  |}}
 === (A2) ===
-Untersuche, ob die Auswahl des Pivotelements einen Einfluss auf das Ergebnis des Sortiervorgangs hat, indem du das Verafhren mit jedem der Elemente als Pivotelement durchführst.
+Untersuche, ob die Auswahl des Pivotelements einen Einfluss auf das Ergebnis des Sortiervorgangs hat, indem du das Verfahren mit jedem der Elemente als Pivotelement durchführst.
 Das sortierte Array erhält man anschließend zuverlässig als:
@@ Zeile 87: / Zeile 87: @@
 <WRAP center round tip 95%>
-Wir können also Arrays mit 3 Elementen auf diese Weise sortieren, dabei spielt es keine Rolle, welches Element man als Pivotelement wählt.
+Wir können also Arrays mit (bis zu) 3 Elementen auf diese Weise sortieren. Dabei spielt es **keine Rolle, welches Element man als Pivotelement wählt**.
 </WRAP>
+==== Arrays mit mehr Elementen ====
+Betrachten wir nun ein Array mit **4 Elementen**:
+{{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:qsortarray02.drawio.png |}}
+Gleichgültig, welches Element man als Pivot Element wählt, erhält man eine Partitionierung, die aus eine linken Array, den Pivot-Element selbst und einem rechten Array besteht. in manchen Fällen sind die linken oder die rechten Arrays leer, was aber kein Problem darstellt, da das durch unseren Basisfall abgedeckt ist.
+{{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:qsortarray03.drawio.png |}}
+Das längste dabei auftretende "Unterarray" hat zwangsläufig die Länge drei, das das Pivotelement selbst bei der Partitionierung "herausgenommen" wird. **Ein Array der Länge drei können wir aber sortieren (s.o.)!**. Wenn wir unsere Quicksort Methode also rekursiv mit einem Array der Länge drei aufrufen, stellt das kein Problem dar.
+Diese Überlegung gilt nun analog für alle längeren Arrays: Nach der Partitionierung eines Arrays der Länge 5 hat das längste Unterarray die Länge 4. Wir wissen aber, dass wir ein Array der Länge 4 sortieren können (s.o.). Ein Array der Länge 6 hat nach der Partitionierung Unterarrays, die nicht länger als 5 sind, und so weiter.
+<WRAP center round tip 95%>
+Es ist also möglich, Arrays mit beliebig vielen Elementen auf diese Weise sortieren. Dabei spielt es **keine Rolle, welches Element man als Pivotelement wählt**. Dieses Sortierverfahren heißt **Quicksort**.
+</WRAP>
+==== Quicksort: Pseudocode ====
+Damit sieht der  Quicksort-Algorithmus im Pseudocode folgendermaßen aus:
+<code>
+quicksort(array): array
+  wenn laenge(array) < 2:
+    return array
+  sonst:
+    pivot = array[0]
+    array kleiner  = (Alle Elemente von Array, die kleiner sind als pivot)
+    array groesser = (Alle Elemente von Array, die größer sind als pivot)
+    return quicksort(kleiner) + pivot + quicksort(groesser)
+</code>
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+Identifiziere im Pseudocode den ''Basisfall'', den ''Rekursionsfall'' und die ''Partitionierung''.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+Verwende die Vorlage https://codeberg.org/qg-info-unterricht/array-summe. Implementiere dort die Methode ''quicksort'' in Java.
+  * Implementiere eine Methode ''kontrollausgabe(array)'', die es dir ermöglicht das Array vor und nach dem Sortieren zu betrachten
+  * Teste deine Methode mit unterschiedlichen Arrays - mit verschiedenen Wertebereichen und Längen. Kontrolliere die Ausgaben.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) ===
+Implementiere eine Methode quicksort, im Musiklisten-Projekt (https://codeberg.org/qg-info-unterricht/musikliste-sortieren) um die Musikliste nach den Ratings zu sortieren.