@skalogryz
I am afraid, the posted algorithm (Same at:
https://wiki.freepascal.org/Array_sort) is wrong.
The original QuickSort uses an arbitrary number (some places call it "Pivot"), to swap every item that is larger to higher indexes and every item that is smaller to lower indexes until the two ranges reach each other, and then one sort is finished and the two sub-parts are sorted again iteratively.
In the posted method not the middle VALUE, but the middle INDEX is fixed (mi, ms). Every time when the two "while" loops are called with CompareFunc, the parameter is NOT the original value, but the original index.
If the array "behaves" well the difference cannot be noticed (typically with low number of data points).
But, if not, when the middle element is swapped with another element, the reference is changing.
Try as an example {7,6,1,2,3,4,5}.
In the original quicksort the check is against VALUE 2. The first swap is 7-2, giving {2,6,1,7,3,4,5} and the check continues from 6 and 1 again, against the original value of 2. In gives a second swap immediately, giving {2,1,6,7,3,4,5}. The process stops here and continues with the split sets of {2,1} and {6,7,3,4,5}. OK, no overlap.
In the posted version the first swap is the same: {2,6,1,7,3,4,5} and the check continues from 6 and 1, but against a value of 7 (new value in the middle position!). So, the first "while" goes up to 7 and the second "while" stops immediately at 1, but as the index of 7 (3) is higher than the index of 1 (2), no swap is done, and the iteration continues with {2,6,1} and {7,3,4,5}, clearly showing that both 6 and 3,4,5 are in the wrong group. From hereon the sorting is correct (in this example, for larger sets it could have the same problem again), giving a final "sorted" set of {1,2,6,3,4,5,7}.
Fixing it is relatively easy, need to add a check that if the swap involved the middle index, than ms need to be updated too. It can occur only once (later the indexes have already crossed it), so mi do not need to be updated.
Move(SwapBuf, pb[hs], Stride);
// begin fix: update ms if the reference point is moved
if li=mi then ms:=hs;
if hi=mi then ms:=ls;
// end fix
inc(ls, Stride); inc(li);
Recent
