Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot
Let $C_1$ and $C_2$ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
Hi @reena_kandari ji,
It depends on how the actual partition function is implemented.
yes, and if I Implements the following procedure than in second case I am getting total $n/2$ swaps.
for(j=r to p+1; j--)
if(i!=j) exchange A[i] with A[j]
if(p!=i-1) exchange A[p] with A[i-1]
For self verification just use some static count variable and print it.
both are the worst cases of quick sort. (assuming pivot is either first or last element)
i am not getting why that "single" swap required if array is sorted in ascending order, as pivot is placed correctly ( say left end element as pivot ) and all right side elements are larger and lhs are smaller ( though nothing is in lhs ).. So where single swap is needed ?
are we swapping element with itself hence "1" swap ?