Quicksort algorithm

Question

I used the quicksort algorithm to sort

11 8 9 4 2 5 3 12 6 10 7

and I got the list:

4 3 2 5 9 11 8 12 6 10 7.

5 was used as a pivot. Now I am stuck. How do I proceed to sort the lowersublist and the uppersublist?

pivot=5 11 8 9 4 2 5 3 12 6 10 7

• Move pivot to position 0 5 8 9 4 2 11 3 12 6 10 7
• i (position 1 = 8)
• j (position 6 = 3) ⇒ swap 8 and 3 5 3 9 4 2 11 8 12 6 10 7
• i (position 2 = 9)
• j (position 4 = 2) ⇒ swap 9 and 2 5 3 2 4 9 11 8 12 6 10 7
• i (position 3 = 4) – no smaller elements than 5 ⇒ swap 5 and 4 4 3 2 5 9 11 8 12 6 10 7 – list after the partition

Answer 1

Quicksort is a recursive algorithm. Once you have sorted the elements by the pivot, you get two sets of items. The first with all elements smaller or equal to the pivot, and the second with all elements larger than the pivot. What you do now, is that you apply quicksort again to each of these sets (with an appropriate pivot).

To do this, you will have to choose a new pivot every time. You can do something like always pick the first element, or draw one at random.

Once you reach a point where a set contains only one element, you stop.

A good way to understand these things is to try to sort a deck of cards using this algorithm. All cards are face down, and you are only allowed to look at two cards at a time, compare these and switch them if necessary. You must pretend to not remember any of the cards that are face down for that to work.