Aufgabe mit Lösung Quicksort-Algorithmus
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ösung
Lösung zu (a) anzeigen
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,17,32], 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, [17, 32], 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. Analog wird weiter vorgegangen, bis alle Elemente des Arrays sortiert sind:
[3, 17, [32], 34, [42], 47, [97, 77, 51], 105]
[3, 17, 32, 34, 42, 47, [77, 51], 97, 105]
[3, 17, 32, 34, 42, 47, [51], 77, 97, 105]
[3, 17, 32, 34, 42, 47, 51, 77, 97, 105]
