0
$\begingroup$

I have an algorithm that does the reverse of partition

Reverse-Partition(A, p, q, r)
  pivot = A[q]
  j = r
  i = q
   while j ≥ p + 1 and i ≥ p
     if A[j] > pivot
      exchange A[j] with A[i]
      i = i − 1
   j = j − 1

I am trying to write an algo that is faster than the above one to get the most optimal run time

Fast-Reverse-Partition(A, p, q, r) 
BEGIN:

For(int i = r; i > (r-q); i--):
   swap A[i] and A[i-(r-q)]

END

In Reverse-partition function, in a given array all element in index q~r are all bigger than pivot element and elements in index p~q are all smaller than pivot so i think with above one we can get same result like Reverse-partition function.
This function has runtime n = r-(r-q)+1 = q+1 so it is faster that reverse-partition function.
Does this make sense? or is my understanding wrong?

$\endgroup$
1
  • $\begingroup$ The algorithms do totally different things. For starters, the second algorithm doesn't use $p$ at all, whilst the first one does use it. $\endgroup$
    – nir shahar
    Oct 7 at 11:28

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.