So I was reading the Hoare's partition part of the Quicksort wiki and it says:
With respect to this original description, implementations often make minor but important variations. Notably, the scheme as presented below includes elements equal to the pivot among the candidates for an inversion (so "greater than or equal" and "less than or equal" tests are used instead of "greater than" and "less than" respectively; since the formulation uses do...while rather than repeat...until which is actually reflected by the use of strict comparison operators
I read through the wiki section and the original paper but I'm not sure how to implement this original method. The part of the original method that I'm not sure about is:
Hoare therefore stipulates that at the end, the sub-range containing the pivot element (which still is at its original position) can be decreased in size by excluding that pivot, after (if necessary) exchanging it with the sub-range element closest to the separation; thus, termination of quicksort is ensured.
The history section of the wiki article states:
Hoare learned about ALGOL and its ability to do recursion that enabled him to publish an improved version of the algorithm in ALGOL.
It seems like the idea is to swap the pivot into place and then not include the pivot in the following partition steps.
Question: Is the pivot swapped into place using this method?
Notably, the scheme as presented below includes elements equal to the pivot among the candidates for an inversion (so "greater than or equal" and "less than or equal" tests are used instead of "greater than" and "less than" respectively ...)
To summarize the Wiki version, it may swap elements equal to the pivot or the pivot itself. This means elements equal to the pivot or the pivot itself can end up anywhere and that no elements can be excluded from later partition steps. The advantage of this is that it eliminates the need for boundary checks. Most current implementations of Hoare partition scheme use this method.
Is the pivot swapped into place using this method?
In the original paper, normally the pivot is not swapped into place. After a partition step, there is a dividing line, values to the left are <= pivot and values to the right are >= pivot, the same as the Wiki version. There is one exception when the partitioning runs into the left or right boundary, in which case one element, which may or may not be the pivot, is swapped into place next to the dividing line and excluded from later partition steps.
Swapping the pivot into place was implemented with an improved version written in ALGOL. The boundary handling was also improved.
Tony Hoare's ALGOL code for partition is algorithm 63 and quicksort is algorithm 64 on page 321 in this snippet of four pages from an ACM article:
https://dl.acm.org/doi/pdf/10.1145/366622.366642
ALGOL is a pass by reference language, so partition() changes the values of I and J. F is the index to the pivot, and X is the value of the pivot.
The code does not swap elements equal to the pivot or the pivot itself, leaving the pivot in its original position. At the end of partition(), there is code that swaps the pivot into place, and then excludes it:
if I < F then begin exchange (A[I], A[F]);
I := I + 1;
end
if F < J then begin exchange (A[F], A[J]);
J := J - 1;
end
The returned values for I and J will exclude the pivot element. The disadvantage of this method is boundary checks (the for loops) are needed.
I converted the ALGOL algorithm to a C++ version, with the partition logic as part of the quicksort function, sorting 64 bit unsigned integers instead of floats. With pseudo-random data, after swapping pivot into place, about half the time J == (I-1) and the other half J == (I-2). In the case of all equal elements, I is incremented to N, J is decremented to M, and the quicksort is completed in one partition step.
static void QuickSort(uint64_t A[], int M, int N)
{
uint64_t P; // pivot value
int L; // pivot index
int I, J;
if(M >= N)
return;
L = (M+N)/2; // Hoare used random value
P = A[L];
I = M;
J = N;
while(1){ // partition step
while(I < N && A[I] <= P) // scan for A[I] > pivot
I++;
while(J > M && A[J] >= P) // scan for A[J] < pivot
J--;
if(I >= J) // break if step done
break;
std::swap(A[I], A[J]); // swap elements
I++; // advance indexes
J--;
}
if(I < L){ // swap pivot into place
std::swap(A[I], A[L]);
I++;
} else if(L < J){
std::swap(A[L], A[J]);
J--;
}
QuickSort(A, M, J); // quicksort left side
QuickSort(A, I, N); // quicksort right side
}