Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #340

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]

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?