def partition (L, first, last) Pick L[first] as the \"pivot\" around which we pa

Question

def partition (L, first, last) Pick L[first] as the "pivot" around which we partition the list p first for current in range Cp+1, last-1): if L[current] LCpl swap CL, current, p+1) swap CL, p, p+1) p 1 return p def generalQuickSort L, first, last) Base case: if first last there is nothing to do Recursive case 2 or more elements in the slice LCfirst. .last] if first last: Divide step p partition CL, first, last) Conquer step general QuickSort (L, first, p-1) general QuickSort CL, p+1, last) Combine step: there is nothing left to do! Suppose that Lis an already-sorted list (in increasing order) of length n. This problem asks you to figure out the worst case running time of the function call generalQuickSort CL, 0, n 1). Start by writing a recurrence relation and then solve it Hint: The complication with quickSort is that the choice of the "pivot" in the partition function affects the sizes of the two subproblems that are solved by the recursive calls. This in turn affects the overall running time quite significantly.

Explanation / Answer

If list is already sorted then in this case worst case happen:

Worst case 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.

The pivot is the smallest element

T(N) = T(N-1) + cN, N > 1

Telescoping:

T(N-1) = T(N-2) + c(N-1)

T(N-2) = T(N-3) + c(N-2)

T(N-3) = T(N-4) + c(N-3)

T(2) = T(1) + c.2

Add all equations:

T(N) + T(N-1) + T(N-2) + … + T(2) =

= T(N-1) + T(N-2) + … + T(2) + T(1) + c(N) + c(N-1) + c(N-2) + … + c.2

T(N) = T(1) + c(2 + 3 + … + N)

T(N) = 1 + c(N(N+1)/2 -1)

Therefore T(N) = O(N2)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.