CSC263H1 Lecture Notes - Lecture 11: Quicksort
Document Summary
The following algorithm sorts an input sequence s in non-decreasing order. Quicksort(s): if |s| 1: return s select pivot p s parition elements of s into else: G = elements of s > p return[quicksort(l), e, quicksort(g)] For the purposes of determinism, select the rst item in s as pivot. To prove worst/best case: a worst/best case input, the time complexity for this input, an argument that this input must be a worst or best case (no other case can take longer/shorter) Want to nd s of size n for which quicksort(s) does at least cn2 comparisons. Let c(n) = # of comparisons performed on [n, n 1, n 2, . , 2, 1]. n will be pivot e = [n] n 1 comparisons l = [ ], g = [n 1, n 2, . C(n) = n 1 + c(n 1), c(1) = 0. = (n 1) + (n 2) + (n 3) + + 1 n(n 1)
