My understanding of quick sort is
- Choose a pivot element (in this case I am choosing middle element as pivot)
- Initialize left and right pointers at extremes.
- Find the first element to the left of the pivot which is greater than pivot.
- Similarly find the first element to the right of the pivot which is smaller than pivot
- Swap elements found in 3 and 4.
- Repeat 3,4,5 unless left >= right.
- Repeat the whole thing for left and right subarray as pivot is now placed at its place.
I am sure I am missing something here and being very stupid. But above does not seems to be working fot this array:
8,7,1,2,6,9,10,2,11 pivot: 6 left pointer at 8, right pointer at 11
2,7,1,2,6,9,10,8,11 swapped 2,8 left pointer at 7, right pointer at 10
Now what ? There is no element smaller than 6 on it's right side. How 7 is going to go to the right of 6 ?
Answer
There is no upfront division between the left and the right side. In particular, 6 is not the division. Instead, the division is the result of moving the left and right pointer closer to each other until they meet. The result might be that one side is considerably smaller than the other.
Your description of the algorithm is fine. Nowhere does it say you have to stop at the middle element. Just continue the execute it as given.
BTW.: The pivot element might be moved during the sorting. Just continue to compare against 6 even if it has been moved.
Update:
There are indeed a few minor problem in your description of the algorithm. One is that either step 3 or step 4 need to include elements that are equal to the pivot. Let's rewrite it like this:
My understanding of quick sort is
- Choose a pivot value (in this case, choose the value of the middle element)
- Initialize left and right pointers at extremes.
- Starting at the left pointer and moving to the right, find the first element which is greater than or equal to the pivot value.
- Similarly, starting at the right pointer and moving to the left, find the first element, which is smaller than pivot value
- Swap elements found in 3 and 4.
- Repeat 3,4,5 until left pointer is greater or equal to right pointer.
- Repeat the whole thing for the two subarray to the left and the right of the left pointer.
pivot value: 6, left pointer at 8, right pointer at 11
8,7,1,2,6,9,10,2,11 left pointer stays at 8, right pointer moves to 2
2,7,1,2,6,9,10,8,11 swapped 2 and 8, left pointer moves to 7, right pointer moves to 2
2,2,1,7,6,9,10,8,11 swapped 2 and 7, left pointer moves to 7, right pointer moves to 1
pointers have now met / crossed, subdivide between 1 and 7 and continue with two subarrays