In CLRS's Introduction to Algorithms,
The following procedure implements quicksort:
QUICKSORT(A; p; r) 1 if p < r 2 q D PARTITION(A; p; r) 3 QUICKSORT(A; p; q-1) 4 QUICKSORT(A; q+1; r)To sort an entire array A, the initial call is QUICKSORT(A; 1; A.length). The key to the algorithm is the PARTITION procedure, which rearranges the subarray A[p..r] in place.
PARTITION(A; p; r) 1 x = A[r] 2 i = p - 1 3 for j = p to r - 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i +1
The quicksort algorithm sorts a set in increasing order, where the pivot is chosen to be the last element in the current array.
I am trying to figure out the worse case and best case to the algorithm.
But I am more interested in whether quicksort will be faster, if the input set is originally more close to the final sorted result. In the concern, I guess the choice of pivot may not matters.
After some thought, the following questions make me think that quicksort will be slower if the input set is more close to the final sorted result.
Is it correct that
when the input set is already in decreasing order, the assignments and exchanges in the for loop in PARTITION will be skipped?
Does quicksort work faster when the input set is already more sorted in decreasing order?
Thanks.