C++ program to sort an array of elements using Quick sort

Aim:

To write a program to sort an array of elements using quick sort technique.

Algorithm:

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

This algorithm sorts an array A of elements N.

1.    [Initialize. ] 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 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 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.

Program code:

Tagged in: ,