## Algorithm Quick sorting (Nonrecursive)

QUICK(A, N, BEG, END, LOC)

Here A is an array with N elements. Parameters BEG and END contain the boundary values of the sub-list of A to which this procedure applies. LOC keeps track of the position of the first element. A[BEG] of the sub list during the procedure. The local variables LEFT and RIGHT will contain the boundary values of the list of elements that have not been scanned.

1.  [Initialize.] Set LEFT:= BEG, RIGHT:=END and LOC:=BEG.
2. [Scan from right to left.]
(a)    Repeat while A[LOC] <= A[RIGHT] and LOC != RIGHT:
RIGHT:=RIGHT-1.
[End of loop.]
(b)    If LOC = RIGHT, then: Return.
(c)    If A[LOC] > A[RIGHT], then:
(i) [Interchange A[LOC] and A[Right].]
TEMP:= A[LOC], A[LOC]:=A[RIGHT], A[RIGHT]:= TEMP.
(ii) Set LOC:= RIGHT.
(iii) Go to Step 3.
[End of If structure.]
3. [Scan from left to right.]
(a)    Repeat while A[LEFT] <= A[LOC] and LEFT != LOC:
LEFT:= LEFT + 1.
[End of loop.]
(b)   If LOC = LEFT, then: Return.
(c)   If A[LEFT] > A[LOC] then
(i) [Interchange A[LOC] and A[Left].]
TEMP:= A[LOC], A[LOC]:= A[LEFT], A[LEFT]:= TEMP.
(ii) Set LOC:=LEFT.
(iii) Go to Step 2.
[End of If structure.]

(Quicksort) This algorithm sorts an array A with N elements.

1. [Initialize.] Set TOP:= NULL.
2. [Push boundary values of A onto stacks when A has 2 or more elements.]
If N > 1, then: TOP: = TOP + 1, LOWER[1]:= 1, UPPER[1]:=N.
3. Repeat Steps 4 to 7 while TOP != NULL:
4.         [Pop sublist from stacks.]
Set BEG:=LOWER[TOP], END:=UPPER[TOP], TOP:=TOP-1.
5.         Call QUICK(A, N, BEG, END, LOC).
6.         [Push the left sublist onto stacks when it has 2 or more elements.]
If BEG < LOC – 1, then:
TOP:=TOP+1, LOWER[TOP]:=BEG,UPPER[TOP]:=LOC-1.
[End of If structure.]
7. [Push the right sublist onto stacks when it has 2 or more elements.]
If LOC + 1 < END, then:
TOP:=TOP+1, LOWER[TOP]:=LOC+1,UPPER[TOP]:=END.
[End of If structure.]
[End of Step 3 loop.]
8. Exit