Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [31.01.2022 16:30] – [Arrays mit mehr Elementen] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:start [31.01.2022 16:39] – [Arrays mit mehr Elementen] sbel
@@ Zeile 93: / Zeile 93: @@
-Betrachten wir nun ein Array mit 4 Elementen:
+Betrachten wir nun ein Array mit **4 Elementen**:
 {{ :faecher:informatik:oberstufe:algorithmen:sortieren:quicksort:qsortarray02.drawio.png |}}
@@ Zeile 100: / Zeile 100: @@
 {{ :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 ====
+<code>