Quick Sort Partitioning Algorithm - Leetcode Solution

After we are done with the partition, we can sort the left part and the right part of the array recursively as shown in the pseudo code below:

Quick Sort Pseudo Code

<code class="EnlighterJSRAW" data-enlighter-language="cpp">
// Sorts the part of array b/w index start and end
QuickSort(A, start, end)
{
// Choosing last element as pivot
pivot = A[end]
// Partitions the array A based on the pivot and returns the position of the pivot
p = partition(A, start, end, pivot)
// Now recursively sort the left part
QuickSort(A, start, p -1 );
QuickSort(A, p + 1, end);
}
</code> 

To implement the partition function used above, we can use Two Pointer Method.

We make make two indexes i and j. i will always point towards the boundary of the elements which are less than the pivot. Since, we don’t know where does the boundary of the pivot end we will initialize i = -1

After that we will start iterating over the array and keep on swapping elements at A[i] with current element, if the jth element is less than pivot.

The pseudocode for the above method is as given below:

Quick Sort Partitioning Pseudo Code

<code> i = -1
pivot = A[end]
for j = 0 to n - 1 {
if  (A[j]  < pivot)  {
i++
Swap(A[i], A[j])
}
}
Swap(A[i+1], A[end])
</code>

Quick Sort Partitioning Visualization

1