Consider the deterministic (i.e., noil-randomized) quicksort which takes the fir

Question

Consider the deterministic (i.e., noil-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 A portion and a | portion. Give the runtime recurrence for this almost-best case Use the recursion tree method to argue why the runtime recurrence solves to (n log n). (You don't need to prove that this guess is correct using big-Oh induction) 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 arc 4 elements on the left side, then the pivot, and finally the last 8 elements on the right side.)

Explanation / Answer

1,2) Run time recurrence of almost best case

Here in our case O(n/3) elements are in one portion and O(2n/3) elements are in other portion so

T(n) = T(n/3) + T(2n/3) + O(n)

Solution of this recurrence is O(nlogn)

13 distinct numbers that causes this almost best case

16, 8, 22 , 30 , 7 ,6 , 9 , 21 , 13 ,28 , 18 ,20 ,11

here 11 is pivot element, after quicksort you will get 4 elements
before pivot and 8 elements after pivot

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---