Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [31.01.2022 16:43] – [Quicksort: Pseudocode] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [24.01.2024 16:34] (aktuell) – [Modellvorstellung] 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]].
 ===== Modellvorstellung =====
-Stell dir vor die Schüler der 7a wollen sich wie die Orgelpfeifen der Größe nach geordnet aufstellen:
+Stell dir vor, die Schüler der 7a wollen sich wie die Orgelpfeifen der Größe nach geordnet aufstellen:
 {{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:unsortiert.drawio.png |}}
-Zunächst wählt man die erste Person als "Vergleichsgröße" aus, der Fachbegriff für das Element, das als Vergleichselement verwendet wird ist **Pivotelement**.
+Zunächst wählt man die erste Person als "Vergleichsgröße" aus, der Fachbegriff für das Element, das als Vergleichselement verwendet wird, ist **Pivotelement**.
 {{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:pivot01.drawio_1_.png |}}
-Jetzt teilt man das Problem in zwei Unterprobleme auf: Alle Schülerinnen die kleiner als das Pivotelement sind stellen sich links davon auf, alle die größer oder gleich sind rechts:
+Jetzt teilt man das Problem in zwei Unterprobleme auf: Alle Schülerinnen, die kleiner als das Pivotelement sind stellen sich links davon auf, alle die größer oder gleich sind rechts:
 {{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:split01.drawio.png |}}
-Das Pivotelement scheidet jetzt aus dem Verfahren aus, es bleibt an dem Platz, an dem es sich jetzt befindet. Jetzt haben wir zwei "kleinere" Sortierprobleme geschaffen: Die Schülerinnen, die links setehen sind ungeordnet, die größeren auf der rechten Seite ebenfalls. Auf jeden Fall -- auch im ungünstigsten((welches ist der ungünstigste Fall?)) -- sind die neuen Teilproblem(e) kleiner als das ursprüngliche Problem.
+Das Pivotelement scheidet jetzt aus dem Verfahren aus, es bleibt an dem Platz, an dem es sich jetzt befindet. Jetzt haben wir zwei "kleinere" Sortierprobleme geschaffen: Die Schülerinnen, die links stehen sind ungeordnet, die größeren auf der rechten Seite ebenfalls. Auf jeden Fall -- auch im ungünstigsten((welches ist der ungünstigste Fall?)) -- sind die neuen Teilproblem(e) kleiner als das ursprüngliche Problem.
 {{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:teilprobleme.drawio.png |}}
@@ Zeile 40: / Zeile 40: @@
 Führe das Verfahren mit Stift und Papier zu Ende, bis du die Schüler nach Körpergröße sortiert hast.
-**Frage:** Was ist der Basisfall beim sortieren der Schülergruppen? Wann kannst du also direkt ohne weitere Überlegung eine sortierte Schülergruppe zurückgeben?
+**Frage:** Was ist der Basisfall beim Sortieren der Schülergruppen? Wann kannst du also direkt ohne weitere Überlegung eine sortierte Schülergruppe zurückgeben?
 ++++ Antwort: | Leere Arrays und Arrays mit nur einem Element stellen den Basisfall dar. Du
@@ 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 110: / Zeile 110: @@
 ==== Quicksort: Pseudocode ====
+Damit sieht der  Quicksort-Algorithmus im Pseudocode folgendermaßen aus:
 <code>
 quicksort(array): array
-  // Basisfall. Leeres Array oder Array der Länge 1
   wenn laenge(array) < 2:
     return array
-  //Rekursionsfall
   sonst:
     pivot = array[0]
-    array kleiner = (Alle Elemente von Array, die kleiner sind als pivot)
+    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.