This worksheet we're going to look at a simplified pseudocode version of the quicksor: algorithm. Kmth's quicksort comparison average (2.12 on page 28 of the text) satisfies the recurrence Co = 0; = 6. Cn=n+1+ C for n>1. If you do some digging, you will find that this is the number of comparisons that Knuth's implementation of quicksortlises in his book The art of computer programming, Vol 3. His algorithm implementation includes a full analysis of a stack and two pointers. We're not interested in this level of detail today, we just want to understand the basic principle of quicksort, derive a similar recurrence for our pseudocode implementation, and solve the recurrence. Here's the procedure: PseudoQuickSort Input: A list L = fal of distinct integers belonging to the set {1,...,n} or an empty list [] If: n=1 or L is an empty list, return L. Else: Set p= (this is called the pivot). Set L L = 11 (create two empty lists). For: 2 Sin If ,

1. If you do some digging, you will find that this is the number of comparisons that Knuth's implementation of quicksortlises in his book The art of computer programming, Vol 3. His algorithm implementation includes a full analysis of a stack and two pointers. We're not interested in this level of detail today, we just want to understand the basic principle of quicksort, derive a similar recurrence for our pseudocode implementation, and solve the recurrence. Here's the procedure: PseudoQuickSort Input: A list L = fal of distinct integers belonging to the set {1,...,n} or an empty list [] If: n=1 or L is an empty list, return L. Else: Set p= (this is called the pivot). Set L L = 11 (create two empty lists). For: 2 Sin If ,