Question

b) Consider the following array values and apply quick sort on it. Only dry run is required but you have to show all steps:
10 3 8 5 12 2 15 4 1

Answer 1

Choose the last element as a pivot and start from the beginning of the array

elements greater go to the right, equal or less are not swapped.

$|10| 3|8|5|12|2|15|4|1| \rightarrow |4| 3|8|5|12|2|15|1|10|$

$|4| 3|8|5|12|2|15|1|10| \rightarrow |15| 3|8|5|12|2|1|4|10|$

$|15| 3|8|5|12|2|1|4|10| \rightarrow |2| 3|8|5|12|1|15|4|10|$

$|2| 3|8|5|12|1|15|4|10| \rightarrow |12| 3|8|5|1|2|15|4|10|$

$|12| 3|8|5|1|2|15|4|10| \rightarrow |5| 3|8|1|12|2|15|4|10|$

$|5| 3|8|1|12|2|15|4|10| \rightarrow |8| 3|1|5|12|2|15|4|10|$ $|8| 3|1|5|12|2|15|4|10| \rightarrow |3| 1|8|5|12|2|15|4|10|$

$|3| 1|8|5|12|2|15|4|10| \rightarrow |1| 3|8|5|12|2|15|4|10|$

$|1| 3|8|5|12|2|15|4|10| \rightarrow |1| 3|8|5|12|2|15|4|10|$

$|1| 3|8|5|12|2|15|4|10| \rightarrow |1| 3|8|5|12|2|15|4|10|$

$|1| 3|8|5|12|2|15|4|10| \rightarrow |1| 3|8|5|12|2|15|4|10|$

$|1| 3|8|5|12|2|15|4|10| \rightarrow |1| 3|8|5|4|2|15|10|12|$

$|1| 3|8|5|4|2|15|10|12| \rightarrow |1| 3|8|5|4|2|15|10|12|$

$|1| 3|8|5|4|2|15|10|12| \rightarrow |1| 3|8|5|4|2|15|10|12|$

$|1| 3|8|5|4|2|15|10|12| \rightarrow |1| 3|8|5|4|2|10|15|12|$

$|1| 3|8|5|4|2|10|15|12| \rightarrow |1| 3|8|5|4|2|10|12|15|$

$|1| 3|8|5|4|2|10|12|15| \rightarrow |1| 4|8|5|2|3|10|12|15|$

$|1| 4|8|5|2|3|10|12|15| \rightarrow |1| 5|8|2|4|3|10|12|15|$

$|1| 5|8|2|4|3|10|12|15| \rightarrow |1| 8|2|5|4|3|10|12|15|$

$|1| 8|2|5|4|3|10|12|15| \rightarrow |1| 2|8|5|4|3|10|12|15|$

$|1| 2|8|5|4|3|10|12|15| \rightarrow |1| 2|4|5|3|8|10|12|15|$

$|1| 2|4|5|3|8|10|12|15| \rightarrow |1| 2|5|3|4|8|10|12|15|$

$|1| 2|5|3|4|8|10|12|15| \rightarrow |1| 2|3|5|4|8|10|12|15|$

$|1| 2|3|5|4|8|10|12|15| \rightarrow |1| 2|3|5|4|8|10|12|15|$

$|1| 2|3|5|4|8|10|12|15| \rightarrow |1| 2|3|5|4|8|10|12|15|$

$|1| 2|3|5|4|8|10|12|15| \rightarrow |1| 2|3|4|5|8|10|12|15|$