Sortieralgorithmus - Stoogesort?

...komplette Frage anzeigen

2 Antworten

  • 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 bewerten Vielen Dank für Deine Bewertung

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

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?