CREATE OWN LIBRARY

Quicksort is a sorting algorithm based on the divide and conquer paradigm. In this algorithm the array is divided into two sub-lists, one sub-list will contain the smaller elements and another sub-list will contain the larger elements and then these sub-lists are sorted again using recursion.

For that these techniques are followed:

1. One element is picked from the list known as the pivot element.

2. The list is then reordered such that the smaller elements of the pivot go to its left sub-list and the greater elements of the pivot element go to its right sublist(the equal element can go either side) and after this reordering, the pivot element will be at its final sorted position.

3. The above two steps are recursively applied to the sublists in a similar way and thus the array gets sorted.

There are various ways to select a pivot element-

1. The first element can be chosen as the pivot element

2. The last element can be chosen as the pivot element

3. Any random element can be chosen as the pivot element

4. The median element can be chosen as the pivot element

Quicksort recursion algorithm is divided into two-part:  1) PARTITION  2) Quicksort 

PARTITION (A, p, r)
	{ 	x = A[r] 		// x is pivot
		i = p – 1
		for (j = p to r – 1)
		{        if(A[j] <= x)
			{ 	i = i + 1
				exchange A[i] with A[j]
			}
		}
		exchange A[i + 1] with A[r]
		return i + 1
}

Quicksort(A, p, r)
{     if(p < r)
	{	q = partition(A, p, r)
		Quicksort(A, p, q – 1)
		Quicksort(A, q + 1, r)
	}
}

Illustrating this procedure by example: 

Suppose there is an array of  7 elements. And the array of unsorted elements is:

low = 0, high = 6 now as per algorithm i = low -1 = 0 – 1 =  -1 and pivot = x = 4

For we travers the array we continue loop  j = low to high -1.

1) So, for first loop  i = -1 and j = 0. Now A[j] > x i.e. 5 > 4 so, no swapping required between i and j.

2) Next (2nd) loop i = -1 and j = 1 below:

 But here again A[j] > x i.e. 7 > 4 so, no swapping required between i and j.

3) Next (3rd) loop i = -1 and j = 2 (Incremented by 1) bellow:

Here A[j] > x i.e. 6 > 4 so, no swapping required between i and j.

4) Next (4th) loop i = -1 and j = 3 (Incremented by 1) bellow:

Here A[j] < x i.e. 1 < 4 so, we first increment i by 1 i.e. i = i + 1 = -1 + 1 = 0 and swap with j.

5) Next (4th) loop i = 0 and j = 4 (Incremented by 1) bellow:

Here A[j] < x i.e. 3 < 4 so, we first increment i by 1 i.e. i = i + 1 = 0 + 1 = 1 and swap with j.

6) Next (4th) loop i = 1 and  j = 5 (Incremented by 1) bellow:

Here A[j] < x i.e. 2 < 4 so, we first increment i by 1 i.e. i = i + 1 = 1 + 1 = 2 and swap with j.

Now end of loop because j = 5 = high -1. So, increment i by 1 i.e. i = i + 1 = 2 +1 = 3 and swap with Pivot i.e. x.

Now the left-hand side of the pivot contains all smaller elements and the right-hand side of the pivot contains all larger elements.

Now, in the same way, we can repeat the left-sub list and the right-sub list. 

Now the sorted elements are:

Recursion Tree (Evaluation of Quicksort):