Java Quicksort mit einem Stack oder Queue in Java

Guten Abend zusammen,

meine Frage ist heute, wie ich den Quicksort Algorithmus nicht rekursiv darstelle, sondern mithilfe eines Stacks oder Queue. Mein normaler Quicksort Algorithmus sieht derzeit noch so aus:

Mir wurde gesagt, wenn man den rekursiven Algorithmus schon hat, könnte man wohl alles so lassen, man müsse nur die Parameter übernehmen und statt dem 2x quicksort(feld,xxxx,x) nur den stack einfügen.
Doch stimmt das? Muss ich nur dort etwas ändern? Müsste ich dann nur statt dem rekursiven Aufruf nur s.push(quicksort(feld,xxxxx,x)) einfügen?

Wäre dankbar für ein paar Ratschläge.

stellt man sich auf ein blatt papier vor, wie eigentlich quicksort funktioniert ( also pivot rauspicken und dann in linke und rechte liste unterteilen), dann würde ich anfangs mittels der Partinionierung,was du ja ab 5.-21. zeile machst nur immer jeweils meine linken teil abarbeiten und den rechten auf den stack packen.
Diesen dann anschließend abarbeiten.
Wikipedia

scheint das genauso zu machen. Sparst dir damit wohl etwas Platz im Stack. Andererseits wird bei einer Rekursion auch der Stack benutzt, nur meistens wird hierbei bevor der branch and link kommt noch Statusregistern und Scratchregister etc.pp mit gespeichert.
Verstehe aber eigentlich nicht, was dir das bringen soll.... Java erledigt fast alles und is eine ziemliche Ressourcensau... von daher würd ich lieber einen guten Programmierstil bevorzugen und der ist mit Rekursion einfach feiner (natürlich nicht zu toppen gegenüber der funktionalen Programmierung ala Haskell/Opal haha )

Quicksort ist von der Art her der Tiefensuche ähnlich. Es setzt also auf Rekursion und LIFO/Stack.
So wie ich das verstanden habe, willst du das so umbauen, dass er der FIFO/Breitensuche ähnlich wird.

Du musst dazu den Algorithmus so umbauen, dass er nicht in eine Rekursion sondern in eine Schleife geht. Statt der rekursiven Aufrufe machst du eine Liste, wo drin steht, was er im nächsten Durchlauf zu bearbeiten hat. Das ist aber nicht ganz trivial, weil du dir Gedanken machen musst, was du in dieser Liste genau abspeicherst.


Btw, Queue != Stack! Was willst du hier genau haben?

Also es geht ja nicht um sauber oder Schnelligkeit, ich will ja einfach nur mein Problem lösen. Und wegen dem Stack != Queue , bin ich ienfach auf der Suche nach einer Lösung für beide Probleme, wobei mir der Stack etwas wichtiger wäre.

Und wie mit einer Liste? Ich muss im Stack ja das alles noch mal neu berechnen und vertauschen. Deshalb sind die Zeilen 24,25 auch ein großes Problem bei mir.

Ich glaube, es besteht noch allgemein Unklarheit, was genau du erreichen willst.
Versuche das doch noch einmal etwas ausführlicher zu schildern.
Geht es dir im Endeffekt nur darum, eine stabile Form von QuickSort zu implementieren?

Gruß

Du scheinst noch nicht zu verstehen, was genau Stack bzw. Kellerspeicher und Queue bzw. Warteschlange bedeutet.

Der rekursive Ansatz verwendet bereits den Stack. Im Stack speichert er die Stellen, bei denen er verzweigt (zB zwei Teillisten). Hier ist das die Stelle, wo er sich selbst aufruft. Er speichert also die Adresse und ackert den neuen Methodenaufruf durch bis dort ebenfalls auf diesen rekursiven Aufruf stolpert. Also speichert er sich wieder die Adresse (schiebt sie auf den Stack) usw. Ruft er sich irgendwann nicht mehr selber auf (Methode endet einfach), dann schaut er in den Stack, in welchen Methodenaufruf er davor war und springt dann dort hin. Die entsprechende Adresse im Stack wird darauf hin gelöscht. usw.
Bei rekursiven Aufrufen muss man daher aufpassen, dass die Rekursionstiefe nicht zu groß wird, da der Stack sonst überläuft.

Bei einer Warteschlange ist das anders. Da es hier keine Rekursion gibt, wird der Stack nicht wesentlich belastet. Man nimmt hier eine Schleife, um die Daten wiederholt zu verarbeiten (das, was die Rekursion sonst immer gemacht hat). Am Ende der Schleife oder am Anfang muss daher immer bestimmt werden, an welcher Stelle er in dieser Iteration was machen soll und wie er an die dafür nötigen Daten herankommt.


Bezogen auf dein Quicksort:
Schreib deine Rekursion so um, dass er nicht das globale Array manipuliert sondern der jeweiligen Rekursion immer die aktuelle Array übergibt. Als Rückgabe (die hast du bisher gar nicht drin) gibt die Rekursion das besser sortierte Array zurück.

Wenn du das dann hast, dann baue das so um, dass statt der Rekursion eine Schleife verwendet wird. Und schon bist du fertig. Und ja, das geht. Jede Rekursion kann man in eine Schleife umwandeln.


Falls du darauf gehofft hast: Fertige Lösungen gibt es nicht von mir. Das Thema bildet die Grundlage für viele Algorithmen, die dir noch begegnen werden. Das musst du verstehen, um später zu begreifen, was überhaupt geschieht.

ich verweise da immer gern auf algolist.net
da werden ganz kurz die datenstrukturen erklärt und verschiedene algorithmen...

gerade datenstrukuren sollte man gekonnt einsetzen können, und sie jedenfalls einmal selbst erstellt haben (auch vielleicht gleich mit generics)
Nur so kann man sich ein Bild darüber machen, was man für welchen Algorithmus braucht. Von daher würde ich sagen zurück zum Anfang. Anscheinend wurde nur drauflos programmiert ohne wirklichen Hintergrund von Rekursion usw.

Ein paar Anhaltspunkte reichen ja meist aus und es fühlt sich aufjedenfall besser an, eigenen Code zu implementieren. Es geht ja um den Lerneffekt und nicht etwa um eine Hausaufgabe