c program and algorithm of quick sort
what is quick sort:-
Quick sort is one of the most efficient sorting technique because it is work on divide and conquer method.
–> the Quick sort algorithm work by partitioning the array to be sorted.
Algorithm:-
Here A is the array with N elements . Parameters BEG and END contain the boundary values of the sublist of A to which this procedure applies . LOC keeps track of the position of the first element A[BEG] of the sublist during the procedure . The local variables
LEFT and RIGHT will contain the boundary value of the list of elements that have not been scanned.
1. 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
(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
3. Scan from left to right
(a). Repeat while A[LEFT]<=A[LOC] and LOC!=LEFT
LEFT=LEFT-1
(b). If LEFT==LOC then Return.
(c). If A[LEFT]>A[LOC] then
(i). Interchange A[LOC] and A[LEFT]
TEMP=A[LEFT]
A[LEFT]=A[LOC]
A[LOC]=TEMP
(ii). Set LOC=LEFT
(iii). GO to step 2
Code:-
Output:-