COMPSCI 61B Lecture Notes - Lecture 36: The Need, Quicksort, Radix Sort
1 Jun 2017
School
Department
Course
Professor
Document Summary
Lab 15, hw 6, and hw 7 are opportunities to replace earlier hws or labs that you missed or did poorly on. Only necessary if you need more points, since we drop two lowest homeworks of 7. One key idea from lecture last time, sorting requires omega(n log n) compares. Sorting provides a solution to the puppy-cat-dog problem. Any lower bound on the number of compares for puppy-cat-dog also applies to sorting. If asking yes/no questions, given q possible answers, you"ll need to ask at least log(q) questions in the worst case to nd the correct answer log(n!) Better asymptotic performance does not imply better real world performance. We don"t always compute for in nitely large n. For large n, log n is almost a constant anyways. Example 1: sleep sort (for sorting integers) (not actually good) For each integer x in array a, start a new program that:
