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?