I want to test time complexity of quickSort but I dont know how to generate arrays for testing best case. My version of quickSort takes as pivot the last element of the array.
3
-
2Did you try all elements being the same? For most "rolled my own" implementations, it is the worst caseJeffrey– Jeffrey2019-10-27 20:56:39 +00:00Commented Oct 27, 2019 at 20:56
-
For best case, the array must already be sorted (in ascending order by default). So generate test case such that ith element of array is strictly greater than (i-1)th element.kiner_shah– kiner_shah2019-10-28 07:28:42 +00:00Commented Oct 28, 2019 at 7:28
-
Already sorted is not for worst case for quickSort? I understood that for the best case the pivot will be in the middle position after partitioning.. but i cannot find out how to generate such an array.Loop24– Loop242019-10-28 17:03:32 +00:00Commented Oct 28, 2019 at 17:03
Add a comment
|
1 Answer
Assuming all the array elements are different, you get the worst case obviously if you always pick either the smallest or largest element. That will give you the worst recursion depth and maximum number of comparisons.
But for the worst case, you will also want many exchanges. Examine how many elements your implementation of quicksort moves when the last element is the smallest, or when it is the largest element in the array. Decide what's worst. Then arrange the numbers in your array so that the last element in each subarray is always the worst case.
