analytics

Monday, February 15, 2016

Perfect pivot quick sort

Suppose you have n items to be sorted, for example:
3,7,15,4,8,2,9,13,11,10,6,12,1,0,14,5
The first step is to take the first four items from the list and arrange them in 2 pairs, so that the least and greatest of the four numbers is the first pair and the two in between are the next pair like so:
3,15
4,7
Now the repeating step is to take the next 2 items from the list and arrange the 3 pairs so the six items are in order reading down the left items then up the right like so:
adding 8,2 to
3,15
4,7
becomes
2,15
3,8
4,7 because these six items in order are 2,3,4,7,8,15
Now we can start a pile with 2 and 15 in it, and our four new numbers are just:
3,8
4,7
and repeat until all the numbers are exhausted for example it continues:
9,13 are added to
3,8
4,7
to get
3,13
4,9
7,8
then the 3 and the 13 join the piles so you have 2,15,3,13 and the four new numbers are:
4,9
7,8
to which you add 11,10 to get:
4, 11
7, 10
8, 9
and 4 and 11 get put onto the pile in progress to have 2,15,3,13,4,11

Now you can see that our bottom two number numbers must eventually be the median numbers of the set because every step found a number less and a number greater than them, and the pile can split in two for items less or greater than those two, this means you will have the perfect pivot to recursively apply the algorithm to the two halves!




No comments:

Post a Comment