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).

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])
      return j

q = Partition(A,p,r)
  • 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 '19 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 '19 at 21:04

Your Answer

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

Browse other questions tagged or ask your own question.