1,353 views
3 votes
3 votes
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?

1 Answer

0 votes
0 votes
If the array is already sorted and we are using fixed partition method quick sort, then the partition takes place in such a way that one side of the pivot contains n-1 elements and other side contains 0 elements and pivot is in the correct  position that gives recurrence as
T(n)=T(n-1)+n

Related questions

3 votes
3 votes
1 answer
1
iarnav asked Jan 14, 2018
2,460 views
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the...
3 votes
3 votes
3 answers
2
Sourajit25 asked Sep 3, 2017
1,612 views
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a ...
2 votes
2 votes
3 answers
3
LavTheRawkstar asked Apr 15, 2017
1,186 views
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9).Analysis the time complexity of Quick sort in the best case.