# change an algo to obtain optimal run time

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?

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