1. Welt
  2. Quests
  3. #1494
Alexander Fufaev

Quicksort-Algorithmus

aus dem Bereich: Quests

Deine Aufgabe ist...

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.

Allgemeine 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 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]

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 1
Gäste online: 1
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.