0
$\begingroup$

I've came across Hoare's partition algorithm in Cormen. After analysis I think that the algorithm isn't working as I expected. Let's suppose that we've array [4,3,2,1], then in my opinion partition is returning 0, so next quicksort calls will be QS(A,1,0), QS(A,1,4), the second one is the same as first call so this array won't be sorted ever (infinite recursion).

Partition(A,p,r)
x = A[p]
i = p-1
j = r+1
while True do
   repeat j-=1
      until x>=A[j]
   repeat i+=1
      until x<=A[i]
   if i<j then
      swap(A[i], A[j])
   else
      return j

QS(A,p,r)
q = Partition(A,p,r)
QS(A,p,q)
QS(A,q+1,r)
$\endgroup$
3
  • 1
    $\begingroup$ Please double check your reasoning, especially the indices. Have you implemented the pseudocode in your favorite programming language? What is the result if you run it? Have you done the exercise "Hoare partition correctness" in the book? QS(A,1,0)? $\endgroup$
    – John L.
    Apr 10, 2019 at 19:15
  • 1
    $\begingroup$ Once upon a time I have analyzed variations of this algo: cs.stackexchange.com/questions/92562/… $\endgroup$
    – Bulat
    Apr 10, 2019 at 21:04
  • $\begingroup$ I also had some trouble implementing this. I was integrating this into a dynamic language where you can easily test the @#$% out of something. In one line I can generate all permiutations of a sequence, sort them, and uniq them to test that they are all identical to each other, and compare to the tested result. I simply iterated on tweaking the details until that test case passed: all possible permutations of 1..9 were being sorted to 1..9. Then added larger test cases. $\endgroup$
    – Kaz
    May 2, 2023 at 5:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.