Aufgabe mit Lösung Quicksort-Algorithmus

Level 2 setzt Schulmathematik voraus. Geeignet für Schüler.

Führe Quicksort-Algorithmus mit dem folgenden Array durch und gib dabei nach jedem Schritt die Teilarrays an:

[34, 105, 3, 47, 32, 42, 17, 97, 77, 51]

Nutze das erste Element als Pivot-Element.

Lösungstipps

Wähle ein Pivot-Element
Teile das Array auf in zwei Teilarrays. Das erste Teilarray enthält Elemente kleiner als das Pivot-Element. Das zweite Teilarray enthält Elemente größer als das Pivot-Element. Analoges Vorgehen mit allen Teilarrays, bis die Teilarrays einelementig sind.
Füge die Teilarrays folgendermaßen zusammen: Linkes Teilarray + Pivot-Element + rechtes Teilarray

Lösungen

Lösung

Nach der Aufgabenstellung muss das erste Element als Pivot-Element gewählt werden. Hier also 34. (Pivot-Elemente werden im Folgenden rot markiert):

[34, 105, 3, 47, 32, 42, 17, 97, 77, 51]

Anschließend wird das Array in zwei Teilarrays aufgeteilt. Ins linke Teilarray platzieren wir alle Elemente, die kleiner sind als 34 und im rechten Teilarray alle Elemente, die größer sind als 34:

[[3, 32, 17], 34, [105, 47, 42, 97, 77, 51]]

In den beiden Teilarrays wählen wir wieder jeweils das erste Element als Pivot-Element. Also 3 im linken Teilarray und 105 im rechten Teilarray. Diese Teilarrays werden jetzt analog weiter aufgeteilt:

[3, [32, 17], 34, [47, 42, 97, 77, 51], 105]

Wie du wahrscheinlich schon gemerkt hast: Es gab keine Elemente, die kleiner waren als Pivot-Element 3. Deshalb war das linke Teilarray leer und wurde weggelassen. Es gab auch keine Elemente, die größer waren als das Pivot-Element 105. Deshalb war sein rechtes Teilarray leer und wurde weggelassen.

Bearbeiten wir zwei Pivot-Elemente gleichzeitig. Nächste Pivot-Elemente wurden bereits im Schritt davor markiert, nämlich 32 und 47:

[3, [17], 32, 34, [42], 47, [97, 77, 51], 105]

Nächste Pivot-Elemente sind 17, 47 und 97:

[3, 17, 32, 34, 42, 47, [77, 51], 97, 105]

Nächstes Pivot-Element ist 77:

[3, 17, 32, 34, 42, 47, [51], 77, 97, 105]

Nächstes Pivot-Element ist 51:

[3, 17, 32, 34, 42, 47, 51, 77, 97, 105]

Damit haben wir ein sortiertes Array erhalten!