1

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

  • Define left and right? You mean left and right of the pivot? Think of it more like "remove pivot from list and add to new list, then append or prepend items in old list to new list". You can do this in practice by cycling the entire list and ignoring the chosen pivot. – Neil May 2 '13 at 12:20
  • I mean left and right pointers. The idea is neither removing the pivot or creating a new list. – NullOrEmpty May 2 '13 at 12:24
  • I see what you mean. I'll write an answer to this then. – Neil May 2 '13 at 12:32
  • After each partitioning operation, the pivot used always ends up at its correct sorted position. It doesn't matter how you chose that pivot. If the data aren't all unique it's possible that some equal-to-pivot values are either/both sides of the final pivot position - usually just one side but it depends how you code the partition - but it doesn't really matter except to note that quicksort isn't stable. – Steve314 May 2 '13 at 13:21
  • That is not right. Check this vector [0,9,1,8,2,7,3,6,4,5] – NullOrEmpty May 2 '13 at 13:23
0

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.

  • Right, I already tried this way and works well. The reason why I am using a middle pivot, is to implement the "median algorithm", that increases quick sort speed by approximating the middle value of a list and use it as pivot: brpreiss.com/books/opus4/html/page500.html (Maybe I should have said that to start with) – NullOrEmpty May 2 '13 at 13:20
  • @NullOrEmpty There's no reason why you shouldn't be able to grab the middle pivot, then swap it with the right-most position and continue the rest of the algorithm normally. – Neil May 2 '13 at 13:33
  • The operation to perform the initial swap would be O(1), so I wouldn't even consider it when considering performance. Rightfully so, if the list is already partially sorted, better to play the odds in your favor. – Neil May 8 '13 at 8:07
  • Could you double check your diagrams? I think something is not right in the one with 6 rows of numbers: the fourth row is identical to the third and not enough like the fifth as it should be. – Don Hatch Apr 2 '15 at 3:19
  • Statements of that form "There's no reason why..." are virtually always wrong, and certainly wrong in this case. A good reason for choosing the middle is to avoid the well-known pathological O(n^2) behavior in typical cases such as when the input is already sorted, or almost sorted, or reverse sorted, or almost reverse sorted. – Don Hatch Apr 2 '15 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.