Quicksort Algorithm in Data Structures

Quicksort is an algorithm of the divide-and-conquer type. That is, the problem of sorting a set is reduced to the problem of sorting two smaller sets. This is called “reduction step”. The reduction step of the Quicksort algorithm finds the final position of one of the numbers.

Quicksort Algorithm in Data Structures

(i) Algorithm: 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.

Step I: [Initialize.] Set LEFT := BEG, RIGHT := END, and LOC := BEG.

Step II: [Scan from Right to Left.]
a) Repeat while A[LOC] <= A[RIGHT] and LOC != RIGHT:
    Set 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.]

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

(ii) Algorithm: (Quicksort.)

SORT(A, N, TOP, LOC, BEG, END, LOWER, UPPER)
This algorithm sorts an array A with N elements.

Step I: [Initialize.] TOP := NULL.

Step II: [Push boundary values of A onto stack when A has 2 or more elements.]
If N>1, then:
Set TOP := TOP + 1,
LOWER[TOP] := 1,
UPPER[TOP] := N.

Step III: Repeat steps 4 to 7 while TOP != NULL:

Step IV: [Pop sublist from STACKS.]
Set BEG := LOWER[TOP],
END := UPPER[TOP],
TOP := TOP – 1.

Step V: Call QUICK(A, N, BEG, END, LOC).

Step VI: [Push 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.]

Step VII: [Push right sublist onto STACKS when it has 2 or more elements.]
If END > LOC + 1, then:
TOP := TOP + 1,
LOWER[TOP] := LOC + 1,
UPPER[TOP] := END.
[End of If structure.]
[End of step 3 loop.]

Step VIII: Exit.