Quicksort algorithm

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

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.

A key component of the algorithm is that the chosen pivot value came from the original list, which means (in your case) the element with the value 5 is now in the correct final position after the first partitioning:

4 3 2 5 9 11 8 12 6 10 7

This should be fairly obvious and follows simple intuition. If every element to the left of an item is smaller than that item and every element to the right is larger, then the item must be in the correct, sorted position.

The insight necessary to understanding the entire Quicksort algorithm is that you can just keep doing this to each of the sublists -- the list of values to the left of the pivot and the list containing all values to the right -- to arrive at the final, sorted list. This is because:

• Each partitioning puts one more element in its proper position
• Each iteration removes one element -- the pivot -- from the list of elements left to process (which is why we'll eventually reach the base case of zero (or one, depending on how you do it) elements)

Let's assume you chose the partition value of 5 based on the following pseudo-code:

Math.floor(list.length / 2)

For our purposes, the actual choice of a pivot doesn't really matter. This one works for your orginal choice, so we'll go with it. Now, let's play this out 'till the end (starting where you left off):

concat(qs([4 3 2]), 5,  qs([9 11 8 12 6 10 7])) = 
concat(qs([2]), 3, qs([4]), 5, qs([9, 11, 8, 6, 10, 7]), 12, qs([])) =
concat(2, 3, 4, 5, qs([6, 7]), 8, qs([9, 11, 10]), 12) =
concat(2, 3, 4, 5, qs([6]), 7, qs([]), 8, qs([9, 10]), 11, qs([]), 12) =
concat(2, 3, 4, 5, 6, 7, 8, qs([9]), 10, qs([]), 11, 12) = 
concat(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Note that each time you see a single call to qs it will follow this pattern:

qs(<some_left_list>), <the_pivot>, qs(<some_right_list>)

And each call of qs on one line results in two more such calls on the following line (representing the processing of both new sublists (except note that I immediately decompose calls to qs on single-value lists)).

It's a good idea to go through this exercise yourself. Yes, with actual pen and paper.