COEN 179 Lecture Notes - Lecture 12: Quickselect, Quicksort, Royal Institute Of Technology

• School: Santa Clara University
• Department: Computer Engineering
• Course: COEN 179
• Professor: Tran

Document Summary

Input: an unsorted array a[lohi], an int k. Easy case: if a is sorted, then kth smallest = kth leftmost. Obvious solution: sort a f ( n es n) return a ceo t k -i] ; Another solution: build a heap from a //o(n) delete min k times // if k = (n/2), then k es n e f ( neg n) Partial quicksort: run partition : 1, 3, 2, 4, 7, 5, 8, 6 omg. Observation: we know the rank of pivot after partitions. rank = 4 since there are 3 elements to left of pivot = 4. If pivot is always max/min, then one partition is empty, C(n) = (n-1) + c(n-1), n > 1. In practice, quick select is fast for many applications. Answer: yes, and it is a simple modification of quick select. Hand pick the pivot instead of leaving it to chance. Ideal choice: choose the median according to the master theorem.