Consider the deterministic (i.e., non-randomized) quicksort which takes the firs
ID: 3669479 • Letter: C
Question
Consider the deterministic (i.e., non-randomized) quicksort which takes the first element as a pivot and uses the partition routine that we covered in class on the quicksort slides. Let's consider another almost-best case for quicksort, in which our chosen pivot always splits the array into a 1/3 portion and a 2/3 portion. (1) Give the runtime recurrence for this almost-best case (2) Use the recursion tree method to argue why the runtime recurrence solves to (n log n). (Yon don't need to prove that this guess is correct using big-Oh induction) (3) Give a sequence of 13 distinct numbers that cause this almost-best case behavior (i.e., the array is split by the function partition such that there are 4 elements on the left side, then the pivot, and finally the last 8 elements on the right side.)Explanation / Answer
Answer for Question 1:
Even the Array is spiting the high and low based on the array values..
So the time complexity for 1/3 or 2/3 will not change i.e o(n log n)
Answer for Question 2:
This happens when the pivot is the smallest (or the largest) element.
Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.
Best-case O(NlogN) The best case is when the pivot is the median of the array,
and then the left and the right part will have same size.
There are logN partitions, and to obtain each partitions we do N comparisons
(and not more than N/2 swaps). Hence the complexity is O(NlogN)
Average-case - O(NlogN)
Answer for Question 3:
These below list of numbers will give the best case time complexity for quick sort ..i.e o(n log n)
1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20