Question

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10. What are the possible values of pivot?

Algorithm coures

Answer 1

Quicksort

It is a highly effective and efficient technique that uses the divide and conquer approach to solve the problem. The main array is subdivided into smaller arrays until and unless we reach the elements in the two arrays one of which holds values smaller than the specified value. The other array keeps on storing the values greater than the specified values. The pivot value serves as the basis for the division of the array. It keeps on changing after the values with the selected pivot value have been separated.

As per given array elements:- 2 5 1 7 9 12 11 10

Here,

If we start with the array,  2 5 1 7 9 12 11 10 we can start of by choosing any element of array as pivot.

Suppose, initially we start of choosing 10 as pivot element, then the low and high pointers are pointing at 2 and 11.

if (Low < pivot) then increment low

else if( High>pivot) then decrement high

else swap(low , high)

New Pivot after the above steps will be decided now. If left >=right, the point where they meet is the new pivot.

So as per the above statement:-

THE POSSIBLE VALUES OF PIVOT ARE:- 10, 11, 9, 7, 1, 2

After choosing 10 as pivot, the sorted array will look like :- 2 5 1 7 9 10 11 12

After choosing 11 as pivot, the sorted array will look like:- 2 5 1 7 9 10 11 12

After choosing 9 as pivot, the sorted array will look like:- 2 5 1 7 9 10 11 12

After choosing 7 as pivot, the sorted array will look like:- 2 5 1 7 9 10 11 12

After this we will choose 1 as Pivot, and our sorted array will become:- 1 5 2 7 9 10 11 12

At last we will chose 2 as pivot and the whole array will be sorted

1 2 5 7 9 10 11 12

Hope this helps :)