Description of quicksort in Design and analysis of algorithms free pdf
Quicksort, like merge sort, is based on the divide-and-conquer. Here is the three-step divide-and-conquer process for sorting a typical subarray A[p ‥r].
Divide:Partition (rearrange) the array A[p ‥r] into two (possibly empty) subarrays A[p ‥q - 1] and A[q 1 ‥r] such that each element of A[p ‥q - 1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q 1 ‥r]. Compute the index q as part of this partitioning procedure.