Quick sort is also known as ‘Partition exchange sort’ works by using a divide and conquer strategy to divide single unsorted array into two smaller sub arrays.
A function Partition is used, by the quick sort algorithm, to divide the array into two sub arrays.
Partition ( A, BEG, END )
Here A is an unsorted array. BEG is the lower bound, END is the upper bound.
Step I : Set LOC = BEG
Step II : Repeat While (True)
Step III : Repeat While (A[LOC] <= A[END]) and (LOC != END)
Step IV : END = END – 1
[End of While Loop]
Step V : If (LOC == END) Then
Step VI : Return LOC
[End of If]
Step VII : Interchange A[LOC] and A[END]
Step VIII : Set LOC = END
Step IX : Repeat While (A[LOC] >= A[BEG]) and (LOC != BEG)
Step X : BEG = BEG + 1
[End of While Loop]
Step XI : If (LOC == BEG) Then
Step XII : Return LOC
[End of If]
Step XIII : Interchange A[LOC] and A[BEG]
Step XIV : Set LOC = BEG
[End of While Loop]
Step XV : Exit
Quick Sort ( A, BEG, END ) :
Here A is an unsorted Array. BEG is the lower bound and END is the upper bound.
Step I : If ( BEG < END ) Then
Step II : X = Partition ( A, BEG, END )
Step III : Call Quick Sort ( A, BEG, X – 1 )
Step IV : Call Quick Sort ( A, X + 1, END )
[End of If ]
Step V : Exit.
Explained using Figure :
Now both sub array are sorted in the same manner.
Pros :- Faster than other algorithm like bubble sort, Selection Sort, and insertion sort. It is one of the most favourable algorithm when speed is big concern. Quick sort can be used to sort arrays of small size, medium, or large size.
Cons :- Complex and massively Recursive.
Myprogworld 