0
$\begingroup$

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?

$\endgroup$
  • 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$ – greybeard Feb 20 '18 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$ – PickleDonk Feb 20 '18 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$ – greybeard Feb 20 '18 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$ – PickleDonk Feb 20 '18 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$ – greybeard Feb 21 '18 at 0:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not really. On cs.stackexchange.com/questions/92562/… I analyzed various variants of the partition algo. $\endgroup$ – Bulat Aug 20 '18 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$ – Apass.Jack Aug 22 '18 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$ – Apass.Jack Aug 22 '18 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$ – Apass.Jack Aug 22 '18 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$ – David Richerby Aug 22 '18 at 15:03
0
$\begingroup$

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?

$\endgroup$
  • 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$ – greybeard Feb 21 '18 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.