Quicksort mit Stack

[java-lehrling]

Hallo zusammen,

bin neu hier und falls meine Frage im falschen Forum gelandet ist, dann sorry. War etwas verwirrt, wo ich dieses Thema posten sollte.

Nun zur Frage:
In den Zeilen 19 und 23 ruft sich die Methode rekursiv auf. Ich soll den rekursiven Aufruf mit Hilfe eines Stacks umschreiben, so dass die Rekursion nicht mehr nötig ist. Ich darf davon ausgehen, dass es eine Klasse Stack gibt die über die Methoden void push(int i) und int pop() verfügt.

Ich habe verstanden was Stacks machen und ich denke ich weiß auch was push und pop machen, aber ich verstehe trotzdem nicht ganz wie ich die rekursiven Aufrufe umschreiben soll.

Kann da jemand helfen ?

Danke schonmal im Voraus.

1 public static void quick_sort_log(int[] A, int links, int rechts) {
2      int i,j,v,t;
3      while (rechts > links) {
4      i = links -1;
5      j = rechts;
6      v = A[rechts];
7      while (true) {
8         do i++; while(A[i] < v);
9         do j--; while (A[j] > v);
10        if (i >= j) break;
11        t = A[i];
12        A[i] = A[j];
13        A[j] = t;
14      }
15      t = A[i];
16      A[i] = A[rechts];
17      A[rechts] = t;
18      if ((i-1-links) <= (rechts-i-1)) {
19         quick_sort_log(A,links,i-1);
20         links = i + 1;
21      }
22      else {
23         quick_sort_log(A,i+1,rechts);
24         rechts = i - 1;
25      }
26   }
27 }

 

[Kababär]

Ich habe diesen Code hier gefunden im Internet. Eigentlich wundere ich mich, wieso man Quicksort mittels Stack implementieren will.
Bisschen weiter runter scrollen, zwei Code und auf Java wechseln. Et voilà, pas cachée.

http://www.geeksforgeeks.org/iterative-quick-sort/

 

[java-lehrling]

Muss ich dann den ganzen rekursiven Ausdruck mit dem entsprechenden Programmteil ersetzen ?

 

[dayaftereh]

Was macht den Rekursion ? Jeder Methoden aufrufen allokiert Speicher auf dem Programm Stack.

Das heißt du muss das auf dem Stack speichern, was in der Methode allokiert wird, um später alles zusammenzufügen...

 

[JStein52]

Muss ich dann den ganzen rekursiven Ausdruck mit dem entsprechenden Programmteil ersetzen ?

Ja. Du brauchst von dem Beispiel die Methoden QuickSort(...), partition(...) und swap(...)
main und diese printArray sind halt nützlich zum Testen