Quick Sorting (Recursive and Non Recursive)

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