Quick Sort

Let us understand the logic behind the Quicksort. Quicksort uses divide and conquer approach. Our first approach is to pick a Pivot element. PIVOT is the element which is sorted itself or we can say that it is placed at such position in the array that’s remain unchanged even after the sorting done.

Example:

5

1

3

2

0

7

As in the Given array we don’t have any idea about the index where the Pivot element is placed. So, we assume the position of PIVOT element in the Given array. For this we can pick our assumed Pivot element:

• From the starting index 0.
• Ending index n-1
• Middle index n/2
• Any random index within the array

Here I have assume PIVOT element is at index 0 i.e. the first element of array as PIVOT element.

As we know that PIVOT element is element which is sorted itself without taking care that element present in the subarray on its L.H.S or R.H.S are sorted or not.

To find the actual PIVOT element , we perform increment operation on array starting from Lower Bound(LB) and decrement operation on array starting from Upper Bound(UB). At which place we get Pivot element we partition the array into two subarrays.

Consider the Given Array = A[]

	LB i++ ====>						j– UB <====
Indexes	0	1	2	3	4	5	6
Values	10	6	3	22	15	87	55
			j	i

In the above figure i will start incrementing until we don’t find the largest element from i and decrementing until we don’t get the smallest number from the assumed PIVOT element(10).

Now i stops at index 3 with element 22 and j stops at index 2 with element 3 which is smallest. But as j < i so we will stop here and swap 10 (assumed pivot element) with element at index j.

	LB i++ =====>						j– UB <=====
Indexes	0	1	2	3	4	5	6
Values	3	6	10	22	15	87	55
			LHS val < j=10 RHS val > j = 10	i

So, we found the Pivot element 10 at position 2 as shown in the above figure and you have noticed that all elements on its L.H.S are smaller and on the R.H.S are larger. We will return the position of PIVOT element while creating logic for Quick Sort and perform partitions along it.

We will create two partition arrays at this stage.
1. Partition — From 0 to 1
2. Partition — From 3 to 6

Again assume pivot element(A[0]) in the both partitioned array and create further sub partition to find next PIVOT element. So, the whole process is repeated until we don’t get the sorted array.