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: