Algorithms – Quicksort and Middle Pivot Explained

algorithmssorting

I am having a head ache understanding quicksort with middle pivot. I found lot of explanations about using left most or right most, but not many about a middle one.

Can I safely assume these?:

  1. If left and right pointers meet at the same position, means that the
    element at that position is at its final sorted position, so I can split the list in two without including that element (list1 length + list2 length = list length -1).

  2. If left and right cross each other ( so left > right), means that no
    element is at its final sorted position yet, so I must split the list in two using left and right as boundaries ( list1 length + list2 length = list length).

Is this right?

Thanks.

Update : The reason why I want to use a middle pivot, is to implement the "median algorithm" that increases QS speed. In this techique, the pivot is selected by approximating the list middle value: http://www.brpreiss.com/books/opus4/html/page500.html

Best Answer

If the array is randomly shuffled, then in theory, one item in the list is as good as another, which means we can pick according to what is most convenient for us. However, it should be said that a middle item would be better suited when the array is almost sorted (or otherwise quicksort would take O(n^2) time). The reason for us to take the middle item is because it is likely representative of an item in which half is less and half is more in this case, and if it were random, it wouldn't make much difference otherwise, would it?

For the sake of this example, lets assume the array is randomly shuffled and so we arbitrarily name the right-most item in the list as the pivot. Starting from the left, compare that number with the pivot. If the number is less than the pivot, go to the next number. If the number is greater than the pivot then you do the following:

If the pivot is not adjacent to the current number, then the pivot switches with its left neighbor. The current number then swaps with the new slot created to the right of the new pivot. If the pivot is adjacent to the current number, then it simply switches position with the current number.

Continue these steps until the index of the current number is equal to or greater than the index of the pivot. Once this is done, perform a recursive call to a sublist of everything on the left side of the pivot and another call to a sublist of everything on the right side of the pivot (assuming length of sublist is 2 or greater).

Lets look at an example:

1 4 8 9 2 3 5

5 is our pivot. Starting with index 0, we get the following operations:

1 4 8 9 2 3 5
^           *
1 4 8 9 2 3 5
  ^         *
1 4 3 9 2 5 8
    ^     *
1 4 3 9 2 5 8
    ^     *
1 4 3 2 5 9 8
      ^ * 
1 4 3 2 5 9 8
      ^ *

End of first pass: Recursive call to left-hand sublist:

1 4 3 2 
^     *
1 3 2 4 
  ^ *  
1 2 3 4 
  ^ *

And recursive call to right-hand sublist:

9 8  
^ *
8 9  
* ^

I hope that clarifies things. Notice how if the current number was greater than the pivot, the current number did not increment. This is because it is replaced with another number which has not yet been handled, and so it too must be checked. I know it isn't exactly what you were doing with middle pivot, but this works just as well.

Related Topic