Frage von SlackCola, 34

Sortieralgorithmus - Stoogesort?

Hallo Community,

Kann mir jmd erklären, wie der Stoogesort funktioniert? Also als Beispiel:

Ich habe die Zahlen 1 - 9, die folgender maßen sortiert sind.

9, 8, 6 ,7, 4, 5, 3, 2, 1

Jetzt möchte ich den Stoogesort Algorithmus anwenden, um diese Zahlen zu sortieren.

Wie genau funktioniert das? Kann es mir bitte jmd. erklären?

Am besten mit Text & kein Code!! :D

Antwort
von slon333, 15
  • Sind das erste und das letzte Element nicht in der richtigen Reihenfolge, so werden sie vertauscht.
  • Sind mehr als zwei Elemente in der Liste, fortsetzen, ansonsten abbrechen.
  • Sortiere die ersten zwei Drittel der Liste
  • Sortiere die letzten zwei Drittel der Liste
  • Sortiere die ersten zwei Drittel der Liste 

Positionen sind 0 - 8, s ist Startposition, e ist Endposition

s=0, e=8

9, 8, 6 ,7, 4, 5, 3, 2, 1 - Das erste und letzte Element werden getauscht

1, 8, 6 ,7, 4, 5, 3, 2, 9 - Es sind mehr als zwei Elemente in der Liste, also fortsetzen

Jetzt sortieren wir die ersten zwei Drittel:

s=0, e=5

9, 8, 6, 7, 4, 5 - Das erste und letzt Element werden getauscht

5, 8, 6, 7, 4, 9 - Es sind mehr als zwei Elemente in der Liste, also fortsetzen.

Jetzt sortieren wir die ersten zwei Drittel dieses Aufrufs

s=0, e=3

5, 8, 6, 7 - Diesmal tauschen wir das erste und letzte Element nicht, weil 5 < 7

Da wir mehr als zwei Elemente haben, geht es weiter

s=0, e=2

5, 8, 6 - Wieder wir nicht getauscht, da 5 < 6. Und es geht weiter, da wir mehr als zwei Elemente haben.

s=0, e=1

5, 8 - 5 < 8, daher kein Tausch. Die Liste hat nur 2 Elemente, daher wird die Rekursion an dieser Stelle abgebrochen. Wir springen jetzt im Code zurück an die Stelle 5, 8, 6

s=0, e=2

5, 8, 6 - Vorhin haben wir die ersten beiden Drittel sortiert (Der Fall mit 5, 8). Dem Algorithmus zufolge müssen wir jetzt die letzten zwei Drittel sortieren.

s=1, e=2

8, 6 - Diesmal wird wieder getauscht, da 8 > 6

6, 8 - Wir haben nur zwei Elemente übrig, d.h. hier greift wieder der Rekursionsanker und wir springen zurück

s=0, e=2

5, 6, 8 - Die ersten beiden und die letzten beiden Drittel wurden sortiert. Nach dem Algorithmus müssten wir jetzt wieder die ersten beiden Drittel sortieren.

So, das geht nun weiter und weiter bis die Liste letztendlich komplett sortiert ist. Das alles aufzuschreiben wäre eine Menge Arbeit, daher breche ich an dieser Stelle ab. Am besten wäre es, wenn du den Code dazu implementierst und dir im Debug-Modus anschaust wie die Liste nach und nach sortiert wird.

Antwort
von Royce, 24

Sind das erste und das letzte Element nicht in der richtigen Reihenfolge, so werden sie vertauscht.

Sind mehr als zwei Elemente in der Liste, fortsetzen, ansonsten abbrechen.

Sortiere die ersten zwei Drittel der Liste

Sortiere die letzten zwei Drittel der Liste

Sortiere die ersten zwei Drittel der Liste

Danke Wikipedia

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten