Horrible sort algorithm, have been bugging me for days. While the list version is simple as heck, in-place version is tough for me because of all of those indexes to remember.
Here’s simple version of the algorithm:
In-place version operates on a continuous array, but still uses lesser-pivot-greater separation model, so we need to emulate those lists in array.
For input lets take start position inside the array and the count of values to emulate sub-array to sort:
As in simple version, if subarray contains only one item (or less), it is sorted and we done with it:
Now for pivot we take
v value, which in our sub-array emulation will actually be
The idea is to move all lesser value to the left part of the array and all greater values to the right part. We start from both ends of the array and go to the center (or wherever these two ‘pointers’ meet). When the left pointer encounters value greater than pivot (and in the left part there should be only lesser values), we have our candidate to move to the right part. The right pointer in the mean time searches for lesser value in the right side (which should be on the left side). Now we have two values which are out of place, so we swap them. Right after that, all values that are left to the ‘left’ pointer and values right to the ‘right’ pointer are exactly where we need them. They’re separated. So we proceed further to the meeting point. We proceed until these two pointers meet each other in some position.
So, first we create pointers:
Now we proceed until they meet each other.
Find the out-of-place value on the left.
Find the out-of-place value on the right.
If it is still not the same value, we swap them:
…and proceed. The comparisons is not strict because of cases when all the values are less than pivot, so we travel to the very end of the array, which is the
right pointer, and we should have possibility to ‘step’ to this position with
When we done,
left will point at the same position, and the pivot is at the start of the subarray. Lets move pivot to the meet point by swapping the very left lesser value with it:
Now the pivot value is between left and right parts. It is in its place, and will not be moved anyway, so we create two new subarrays without it. The left one starts from the
start and up to the new
left position. The right one starts from the pivot position to the end of original subarray (
count). These two lists should be sorted now:
The full code: