0
$\begingroup$

Regarding this algorithm:

Algo(A, p, r)
if p ≤ r then
  q ← Partition(A,p,r)
if q == r then
  return A[q]
else
  return Mystery(A,q+1,r)
end
end

While partition is:

Partition(A,p,r)
x=A[r]; j=r; i=p-1;
While true
    repeat j ← j - 1
       until A[j]<x
    repeat i ← i +1
       until A[i] >= x
    if i<j
       then A[i] ←→ A[j] % swap
       else A[j+1] ←→ A[r]
          return j+1

I need to explain what Algo do.

So Partition is from Quicksort, dealing with the pivot.

Partition basically returns the index of the pivot, and then in Algo, we are taking the index and assigning it into q.

We are keep doing it until q==r, but I don't understand what Algo really does, is the output, and what is the running time of something like this.

Any help will be amazing!

Thanks a lot!

$\endgroup$
2
  • $\begingroup$ What is the Mystery function? Is it the same as Algo? $\endgroup$ – Nathaniel Apr 28 at 17:38
  • $\begingroup$ It's a... Mystery ;) $\endgroup$ – Steven Apr 28 at 18:29

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.