Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [31.01.2022 16:16] – [Arrays mit zwei oder mehr Elementen] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [31.01.2022 16:53] – [Quicksort: Pseudocode] sbel
@@ 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 86: / Zeile 86: @@
+<WRAP center round tip 95%>
+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.