Witam
Przeszukałem internet i nigdzie nie mogę znaleŹć quicksorta nierekurencyjnego napisanego w Pascalu.
Znalazłem szukany algorytm w książce N. Wirth'a , który wygląda tak :
PROCEDURE NonRecursiveQuickSort;
CONST M = 12;
VAR i, j, L, R, s: INTEGER; x, w: Item;
low, high: ARRAY M OF INTEGER; (*index stack*)
BEGIN s := 0; low[0] := 0; high[0] := n-1;
REPEAT (*take top request from stack*)
L := low[s]; R := high[s]; DEC(s);
REPEAT (*partition a[L] ... a[R]*)
59
i := L; j := R; x := a[(L+R) DIV 2];
REPEAT
WHILE a[i] < x DO INC(i) END ;
WHILE x < a[j] DO DEC(j) END ;
IF i <= j THEN
w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j-1
END
UNTIL i > j;
IF i < R THEN (*stack request to sort right partition*)
INC(s); low[s] := i; high[s] := R
END ;
R := j (*now L and R delimit the left partition*)
UNTIL L >= R
UNTIL s = 0
END NonRecursiveQuickSort
Książka jest dostępna tutaj http://www.oberon.ethz.ch/WirthPubl/AD.pdf = strona 55
Po skopjowaniu algorytmu i próbie odpalenia- wyświetla błędy w pętlach
WHILE a[i] < x DO INC(i) END ;
WHILE x < a[j] DO DEC(j) END ;
gdzie widać, że ten End odnosi się do nie wiadomo czego, więc go usunąłem. Dodałem jeszcze begin i end przy pętli if i<=j oraz if i<R. Tak to wygląda po modyfikacji:
s := 0;
low[0] := 0;
high[0] := n-1;
REPEAT (*zabierz z top prosbe ze stosu*)
L := low[s];
R := high[s];
DEC(s);
REPEAT (*dzial a[L] ... a[R]*)
i := L;
j := R;
x := d[(L+R) DIV 2];
REPEAT
WHILE d[i] < x DO INC(i); //
WHILE x < d[j] DO DEC(j); //
IF i <= j THEN
BEGIN
w := d[i];
d[i] := d[j];
d[j] := w;
i := i+1;
j := j-1;
END;
UNTIL i > j;
IF i < R THEN (*prosba stosu zeby sortowac prawy dzial*)
BEGIN
INC(s);
low[s] := i;
high[s] := R;
END ;
R := j (*teraz L i R ograniczaja lewy dzial*)
UNTIL L >= R;
UNTIL s = 0;
I tutaj pojawia się problem bo wydawało by się że algorytm z książki powinien działać, a tutaj sortuje mi dobrze ale gdzieś do połowy tablicy. Jeśli ktoś wie jak zmusić ten algorytm do działania bardzo proszę o pomoc.
Pozdrawiam i z góry dzięki