Question

The quicksort is an example of a divide and conquer algorithm in that it divides the sorting problem into smaller problems by dividing the list of items to be sorted into smaller subsets. The pivot is the mechanism that is used to segment the list. Describe how the quicksort works including a discussion of the pivot, how it is selected, and why the pivot is important to the quicksort.

Answer 1

Hello Student,

Working of Quicksort Algorithm:

In quicksort algorithm we first consider an element of the given unsorted array as a pivot element whether it be the first, last or the middle element to place elements smaller than the pivot to left and greater to right side. Also, we point first index element as low index and last index element as high index (depending on pivot’s location). Then simply moving the low index to right if the pointed element is lesser compared to pivot and moving the high index to left if pointed element is greater compared to pivot. But if low index points to greater element and high index points to smaller element than pivot then swap the low and high index pointed elements. At last if low index becomes equal to high index then swap the element with pivot.

In quicksort, the array is divided into lower side and greater side of pivot i.e. 2 parts and the same above method is applied to both part and at last joined all together with the pivot to give the whole sorted array.

Example-

L= low index, H= high index, P= pivot.

Here we selected last 48(last element) as pivot, first 48(first element) as low index and 26(2^nd last element) as high index.

48	37	64	96	75	12	26	48
L						H	P

Swapped low and high element as low was > and high was < than pivot.

26	37	64	96	75	12	48	48
L						H	P

Low index moved to right until greater element than pivot was pointed.

26	37	64	96	75	12	48	48
		L				H	P

Swapped low and high element as low was > and high was < than pivot.

26	37	48	96	75	12	64	48
		L				H	P

High index moved to left until lesser element than pivot was pointed.

26	37	48	96	75	12	64	48
		L			H		P

Swapped low and high element as low was > and high was < than pivot.

26	37	12	96	75	48	64	48
		L			H		P

Low index moved to right until greater element than pivot was pointed.

26	37	12	96	75	48	64	48
			L		H		P

Swapped low and high element as low was > and high was < than pivot.

26	37	12	48	75	96	64	48
			L		H		P

High index moved to left until lesser element than pivot was pointed.

26	37	12	48	75	96	64	48
			L	H			P

Here we get Low = High, thus swapped it with pivot.

26	37	12	48	75	96	64	48
			L=H				P

Divided the array in left side and right side according to pivot.

quick sorting the Left side.

26	37	12
L	H	P

  

High index moved to left until lesser element than pivot was pointed.

Here we get Low = High, thus swapped it with pivot.

26	37	12
L=H		P

Again,

12	37	26
L	H	P

  

Low index moved to right until greater element than pivot was pointed. Here we get Low = High, thus swapped it with pivot.

12	37	26
	L=H	P

So, left side of pivot is sorted.

12	26	37

     

Quick sorting the Right side.

75	96	64	48
L		H	P

Swapped low and high element as low was > and high was < than pivot.

64	96	75	48
L		H	P

High index moved to left until lesser element than pivot was pointed. Here we get Low = High, thus swapped it with pivot.

64	96	75	48
L=H			P

Again,

48	96	75	64
L		H	P

Low index moved to right until greater element than pivot was pointed.

48	96	75	64
	L	H	P

High index moved to left until lesser element than pivot was pointed. Here we get Low = High, thus swapped it with pivot.

48	96	75	64
	L=H		P

So, right side of pivot is sorted.

48	64	75	96

Thus, After re-joining the left side, pivot, right side we get the sorted array.

12

26

37

48

48

64

75

96

---------------------------------------------------------------------------------------------------------------------------------------------------------

THANK YOU!

LIKE THE ANSWER IF IT HELPED YOU