If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at 1 and 1, then what would happen? If they are switched, nothing is really sorted. And the same goes for the two indexes both landing on numbers greater than the pivot, for example, 7 and 7. How would Hoare's algorithm handle such a case?
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ Please improve the presentation of the list. Far as I remember, Hoare presented two variants of what was later to be called Hoare partition scheme (one titled "Partition without Exchange") in "the original article": please quote the algorithm you are referring to, or otherwise unambiguously identify it. $\endgroup$– greybeardCommented Feb 20, 2018 at 23:03
-
$\begingroup$ @greybeard the original article is here (I was using the version first described, at the very beginning): en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme $\endgroup$– PickleDonkCommented Feb 20, 2018 at 23:15
-
$\begingroup$ (I thought the 1961 presentation of ACM algorithms 63 & 64 pre-dated wikipedia as well as the article in The Computer Journal.) $\endgroup$– greybeardCommented Feb 20, 2018 at 23:28
-
$\begingroup$ @greybeard from my understanding of quicksort from the wikipedia article, using the hoare method, you would have two indexes: i, at the first element in the array, and j, at the last element in the array. Then the elements at these indexes would be compared: if i is <= pivot and j >= pivot, the elements are swapped. Then, i is incremented, and j is decremented. The comparison happens again and again, until i and j cross each other. But if the elements they are switching are both less than the pivot, or both greater than the pivot, then what happens? $\endgroup$– PickleDonkCommented Feb 20, 2018 at 23:42
-
$\begingroup$ One has to be careful to tell/keep element at index from index in comparisons: the first is used to control data movement, the latter for loop termination. $\endgroup$– greybeardCommented Feb 21, 2018 at 0:24
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
11
You've misunderstood the algorithm and it doesn't have the behaviour you suggest.
Let the pivot value be $p$. The algorithm searches from the left for a value $\ell\geq p$ and from the right for a value $r\leq p$. It then only swaps them if they're in the wrong order relative to each other, i.e., if $\ell>r$, so it will never exchange two identical array elements.
In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.
answered Aug 20, 2018 at 11:11
-
$\begingroup$ Not really. On cs.stackexchange.com/questions/92562/… I analyzed various variants of the partition algo. $\endgroup$– BulatCommented Aug 20, 2018 at 11:55
-
$\begingroup$ This answer contradicts the description of the algorithm at wikipedia item, which reads, "Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one lesser or equal, that are in the wrong order relative to each other. The inverted elements are then swapped" (bold font added by me). Note the "equal to" part in the description is critical in this question and all its answers. $\endgroup$– John L.Commented Aug 22, 2018 at 1:39
-
$\begingroup$ Of course, this answer might be updated to claim that the algorithm can use extra steps to detect whether the elements encountered are equal (to the pivot value) and NOT exchange the two elements in those situations. However, we will then have, apparently, an uncommon version of the algorithm that is not the topic of this question. $\endgroup$– John L.Commented Aug 22, 2018 at 1:48
-
$\begingroup$ If we just want to answer the specific question of OP, "What if ... both land on Values Less than Pivot?" (not on values equals to Pivot), then this answer may make more sense, since if the algorithm exchanges two equal elements, then both elements will must be equal to the Pivot. $\endgroup$– John L.Commented Aug 22, 2018 at 2:04
-
$\begingroup$ @Apass.Jack OK, fixed. But neither the version I originally described nor the version in the Wikipedia article will ever swap identical elements so I'm not sure there was a huge issue. $\endgroup$ Commented Aug 22, 2018 at 15:03
$\begingroup$
$\endgroup$
1
Here is the pseudocode at wikipedia on quicksort using the Hoare partition scheme:
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do i := i + 1 while A[i] < pivot
do j := j - 1 while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
The indexes never start at the same number in partition:
hi is at least lo+1 (j is at least i+3).
They start indexing "from the ends" to "meet in the middle".
Assuming the list a, g, e, g, a from the question, indexing starting at 1 and pivot "magically" assuming e (the pseudo-code shown would set it to a), i gets initialised to 0 and i to 6 in the first execution of partition.
The 1st "do - while" in the "forever-loop" would set i to 1 unconditionally and to 2 because A[i], which is A[1], (a) is smaller than pivot(e).
The 2nd "do - while" would stop right after setting j to 5:
A[5] already is smaller than pivot.
i is smaller than j: partition isn't done
i and j index a pair of elements in A deserving a swap - guess what?
-
1$\begingroup$ PickleDonk, as everyone else, is invited to try and make this useful as can be. "Everyone" presenting an example with element values possibly confused with index values in an introductory context should be tarred and feathered. $\endgroup$ Commented Feb 21, 2018 at 6:19