Search code examples
structurequicksort

Quicksort where the pivot is chosen randomly


I have the following question:

Let A=[84,33,72,60,22,63] be an array of numbers. 
We want to sort A using Quicksort where the pivot is chosen randomly.
At the end of the **first iteration** it might be that A will be?
1.A=[63,33,72,60,84,22]
2.A=[84,33,72,60,22,63]
3.A=[22,33,72,60,84,63]

I would love an explanation, I can not understand why I can not get to one of the answers shown. Thanks in advance.


Solution

  • There are 6 numbers in this array hence if you randomly pick a pivot point the first iteration might have 6 possible results. For example if 84 is picked at random the first iteration would result in A = [33,72,60,22,63,84] As you can see 84 was the biggest number in the list so all the entries on the right was moved to the left during the search.