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

2 Antworten

slon333

23.02.2016, 12:12

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.

Royce

23.02.2016, 10:59

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

Ähnliche Beiträge

Sortieralgorithmus Insertion Sort als Code?

Ich verstehe nicht, wie der Algorithmus funktionieren soll??

Wieso wird i zu j umbenannt?

Was heißt solange j>0 und sortiert[j-1] > buecher i? Wieso das j-1 dort?

Wieso j= j-1 und was passiert bei sortiert[j]= buecher[i]

Der Algorithmus ist ein Sortier Algorithmus Insertion Sort

Bitte um Hilfee

...zum Beitrag

Sortieralgorithmus Flussdiagramm?

Hallo,

ich habe versucht folgende Aufgabe mittels einem Flussdiagramm darzustellen und wollte mal nachfragen ob das so funktioniert:

"Nach Eingabe einer Liste[n], welche n Zahlen enthält, soll das Programm die Zahlen der Liste von Position 1 bis Position n aufsteigend sortieren und anschließend die sortierte Liste wieder ausgeben."

Ich habe den Bubble-Sort Algorithmus verwendet.

MMN kommt die Liste korrekt sortiert heraus. Liege ich da richtig oder ist mir bei zeichnen des Diagramms ein Fehler unterlaufen?

MFG

...zum Beitrag

Sortieralgorithmus selection sort?

Hey, ich soll ein zweiseitiges Handout zu den Sortieralgorithmus selection sort erstellen, wobei ich

auf die grundlegende Vorgehensweise dieses Algorithmus eingehen soll
und ich brauche die Java- Methode zur Implementierung, wobei man davon ausgehen soll, dass ein Array von int- Werten zu sortieren ist.

Dazu wurde uns auch Material gegeben, welches ich als Foto anhängen werde.

Ich freue mich auf Rückmeldungen!

...zum Beitrag

Welchen Algorithmus verwende ich, um 50 Zahlen mit möglichst wenig Vergleichen und Vertauschungen zu sortieren?

Die Aufgabe ist, einen beliebigen Sortieralgorithmus aus berliebiger Quelle in Java zu implementieren, um bis zu 50 Zahlen zu vergleichen. Gewertet wird nur die möglichst geringe Anzahl an Vergleichen und Vertauschungen. Der Rest ist egal. Keine Zahl kommt Zweimal vor. Welcher Algorithmus eignet sich da am besten?

...zum Beitrag

Wie funktioniert der (YouTube) Algorithmus?

Hallo Community, wie funktioniert der Algorithmus auf YouTube, Instagram und Tik Tok. Wo nach sortiert er, wonach entscheidet er? Gibt es Tips und Tricks um den Algorithmus für sich zu nutzen?

...zum Beitrag

Pyhton - Sortieralgorithmus?

Hallo Zusammen,

Aktuell müssen wir in der Berufsschule ein Lottozahlen Generator schreiben, das dieser 6 Zahlen ausgibt hab ich schon geschafft.

Das zweite wäre das wir die Ausgaben in der in der gezogenen sowie aufsteigend sortierten Reihenfolge ausgeben sollen. Ich hatte schon im Netz gesucht aber nichts gefunden, und jeder Lottozaglengenerator verweist auf die "sort" Funktion hin die wir nicht benutzen dürfen.

Weiß jemand daher wie man diesen Algorithmus schreibt ?

Grüße, YouGetMyAnswer

...zum Beitrag

LinkedList in Java sortieren beim Einfügen eines neuen Elements?

Ich habe hier den Code geschrieben, um ein neues Element einzufügen und danach die Liste zu sortieren.

Ich weiss, dass beides (Algorithmus für einfügen & Algorithmus fürs Sortieren) einzeln eigentlich funktionieren sollte. Aber die Kombination davon in einer Methode scheitert. Sieht jemand den Fehler.

Herzlichen Dank im Voraus!

...zum Beitrag

Python: Integer in Strings sortieren?

Wenn ich eine Liste mit os.listdir() erstelle und dann sortiere dann wird es nicht richtig sortiert weil es als Strings sortiert wird z.B.: ["Code-1.txt,"Code-10.txt","Code-11.txt"]... Statt: ["Code-1.txt","Code-2.txt","Code-3.txt"]... Wie kann ich die Liste so sortieren dass es nach Integern sortiert wird und nicht nach Strings?

...zum Beitrag

Java Bubble Sort Algorithmus programmieren wer kann mir helfen (bitte keine Lösung schreiben sondern nur Tipps geben)?

Die Aufgabenstellung lautet:

"Damit Sie sehen wie nervig das Sortieren eines Arrays wirklich sein kann wenn man es selbst programmieren muss: implementieren Sie einen einfachen Sortieralgorithmus in einer Methode namens 'bubblesort'. Diese Methode erwartet einen Parameter 'x' wie in der letzten Aufgabe, und verfährt auch genauso mit ihm. Die Sortierung wird wie folgt durchgeführt: angefangen beim zweiten Array-Element (also mit Index 1) prüfen Sie für alle Elemente, ob sie kleiner sind als ihr Vorgänger, und vertauschen sie sofort falls ja. Dies wird so lange durchgeführt, bis bei einem kompletten Durchlauf durch das Array (beginnend bei Index 1) keine Vertauschung mehr vorgenommen werden muss, in diesem Fall ist das Array sortiert. Falls das Array 0 oder 1 Elemente hat muss nichts getan werden da solche Arrays bereits sortiert sind (warum?). Tipp: die perfekte Gelegenheit eine do/while-Schleife zu benutzen!"

Mit freundlichen Grüßen

...zum Beitrag

Java: Kann mir jemand diese Methode erklären, die eine Karawane bestehend aus Kamelen sortiert?

Hallo,

kann mir jemand diese Methode erklären, die eine Karawane bestehend aus Kamelen sortiert?

public void sortieren() {
  if (Erstes.Naechstes != null) {
    Kamel einKamel = sucheAlphaMin();
    entferne(einKamel);
    sortieren();
    fügeHinzu(einKamel);
  }
}

private Kamel sucheAlphaMin() {
  Kamel min = Erstes;

  for (Kamel k = Erstes; k != null; k = k.Naechstes)
    if (k.getName().compareToIgnoreCase(min.getName()) < 0) {
      min = k;
    }

    return min;
}

...zum Beitrag

Wie funktioniert der bubble sort Algorithmus?

Kann jemand mal erklären wie bubble sort funktioniert? Warum gibt es ihn wenn er doch uneffektiv ist?

...zum Beitrag

Python nach Größe Sortieren

Hallo,

Ich möchte, dass mich Python nach 3 beliebigen Zahl abfragt und diese dann sortiert.

Wie gehe ich am Besten dabei vor ?

Danke Edisboy

...zum Beitrag

Welcher Sortieralgorithmus ist unter welchen Umständen der schnellste?

Nabend.

Da ich mich ja mit der Programmierung beschäftige, habe ich versucht, einige Sortieralgorithmen in C++ nachzuprogrammieren (und mir danach die schnelleren Versionen aus dem Netz raus zu suchen). Dann wollte ich anhand einer Liste von 500.000 Elementen testen, welcher Algorithmus der Schnellste ist.

Getestet habe ich bisher std::sort, Quick Sort, Insertion Sort und Timsort. std::sort war bei der unsortierten Liste zwei Millisekunden schneller als Timsort, danach folgte Insertion Sort und Quick Sort war letzter. Wenn ich aber ein neues Element zu der sortierten Liste hinzugefügt habe, war Timsort der schnellste Algorithmus mit sage und schreibe 0 Mikrosekunden. Danach folgten Insertion Sort, std::sort und zu guter letzt war mal wieder Quick Sort fertig.

Wenn ich das ganze kurz zusammenfassen sollte, würde ich sagen, dass Timsort an dieser Stelle der beste Sortieralgorithmus ist, auch wenn er zwei Millisekunden langsamer bei der Sortierung einer komplett unsortierten Liste als std::sort ist. Zwei Millisekunden sind vernachlässigbar, vor allem, wenn std::sort bei der Sortierung der bereits sortierten Liste mit einem neuen Element 9 Millisekunden braucht, während Timsort nicht mal eine Mikrosekunde benötigt.

Gibt es Sortieralgorithmen, die noch schneller sind als die vier vorhin genannten? Oder welche anderen Szenarien könnte ich testen?

Gruß

...zum Beitrag

Euklidischer Algorithmus mit drei Zahlen?

Moin!

Kann man den Euklidischen Algorithmus auch mit drei Zahlen anwenden?
Vielen Dank im Voraus!

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen