Quick Sort Question

Question

Can anybody please help me out with this sorting question? I am new to the topic of sorting algorithm and just trying to complete the same.

Ques: Sort the below using Quick sorting algorithm

15, 10, 13, 9, 12, 7.

I started solving this and tried a lot.

Selected the last element as Pivot and continuously checked for the comparison with the pivot.

In Step 4 when (i) which points to first element and (j) which also points to first element of the array which is 15 gets swapped with the pivot value 7.

After this i just got confused that how to proceed further.

Partially Solved Answer: Let (i) point to 15 which is the first element and (j) point to the last element and Pivot point to 7 as the last element.

Step1: 15, 10, 13, 9, 12, 7

Condition Check: 

i<Pivot and j>Pivot
15 < 7 and 12 > 7
false and true 

So (i) will remain pointing to 15 which is at 0th position and (j) will move towards let and will point to 9.

15=>(i), 10, 13, 9=>(j), 12, 7=>PIVOT 

Step 2: 

Condition Check: 15 < 7 and 9 > 7 false and true

(i) will remain pointing to 15 which is at 0th position and (j) will will towards left and will point to 13.

15=>(i), 10, 13=>(j), 9, 12, 7=>PIVOT 

Step 3:

Condition Check: (i) < Pivot and j > Pivot 15 < 7 and 13 > 7 false and true

(i) will remain pointing to 15 which is at 0th position and (j) will move towards left and will point to 10.

15=>(i), 10=>(j), 13, 9, 12, 7=>PIVOT 

Step 4:

Condition Check: i < Pivot and j > Pivot 15 < 7 and 10 > 7 false and true

(i) will remain pointing to 15 which is at 0th position and (j) will move towards left and will point to 15.

Now (i) and (j) point to the same element so will be swapped 0th element 15 will 7(pivot and last element)

7, 10, 13, 9, 12, 15.

Thanks for the help.

Answer 1

• $15,10,13,9,12,7$

Select last element as pivot and then make two sets separated by the pivot

$\varnothing, 7,\{15,10,13,9,12\}$

The first set of elements lower than $7$ is empty, so it is sorted already. Now you continue with the set on the right.

• $15,10,13,9,12$

Select last element as pivot and then make two sets separated by the pivot

$\{10,9\},12,\{15,13\}$

You have now two sets to sort :

• $10,9$

Select last element as pivot and then make two sets separated by the pivot

$\varnothing,9,\{10\}$

everything sorted

• $15,13$

Select last element as pivot and then make two sets separated by the pivot

$\varnothing,13,\{15\}$

everything sorted

Putting the whole algorithm together we get :

$\begin{cases} \{15,10,13,9,12,7\}\\ \{\varnothing, 7,\{15,10,13,9,12\}\}\\ \{\varnothing, 7,\{\{10,9\},12,\{15,13\}\}\}\\ \{\varnothing, 7,\{\{\varnothing,9,\{10\}\},12,\{\varnothing,13,\{15\}\}\}\}\\ \{7,9,10,12,13,15\} \end{cases}$

Of course with an algorithm that works on an array, you have to manipulate the indices so that braces and $\varnothing$ are hidden.

$\begin{cases} [15,10,13,9,12,7]\\ [7,15,10,13,9,12]\\ [7,10,9,12,15,13]\\ [7,9,10,12,13,15]\\ \end{cases}$