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!