#Quicksort

Question

In Quicksort of the following numbers, if the pivot is chosen as the first element, what will be the order of the numbers after the use of partition function? Assume we are sorting in increasing order. 11, 15, 9, 13, 17, 7, 5, 12, 6, 18

Answer 1

array[ ] = { 11, 15, 9, 13, 17, 7, 5, 12, 6, 18 }

indexes :    0    1   2   3    4   5  6   7   8    9

pivot = array[0] = 11; i = 0 and j = 1

we traverse the entire array from left to right ie from j=1 to j=9 -

1. array[ j ] > pivot ie 15 > 11 → j++
2. array[ j ] < pivot ie 9 < 11 → i++ then swap array[ i ] and array[ j ] then j++. Now, array[ ] = { 11, 9, 15, 13, 17, 7, 5, 12, 6, 18 }
3. array[ j ] > pivot ie 13 > 11 → j++
4. array[ j ] > pivot ie 17 > 11 → j++
5. array[ j ] < pivot ie 7 < 11 → i++ then swap array[ i ] and array[ j ] then j++. Now, array[ ] = { 11, 9, 7, 13, 17, 15, 5, 12, 6, 18 }
6. array[ j ] < pivot ie 5 < 11 → i++ then swap array[ i ] and array[ j ] then j++. Now, array[ ] = { 11, 9, 7, 5, 17, 15, 13, 12, 6, 18 }
7. array[ j ] > pivot ie 12 > 11 → j++
8. array[ j ] < pivot ie 6 < 11 → i++ then swap array[ i ] and array[ j ] then j++. Now, array[ ] = { 11, 9, 7, 5, 6, 15, 13, 12, 17, 18 }
9. array[ j ] > pivot ie 18 > 11 → j++

swap pivot and array[ i ]. Now, array[ ] = { 6, 9, 7, 5, 11, 15, 13, 12, 17, 18 }

Comments

thanks bro!

Answer 2

I am getting answer as

6,7,9,5,11,15,13,17,12,18

But it is not matching with the options given in the question.