CS61B Lectures #29
• Lower bounds on sorting by comparison • Distribution counting, radix sorts
Readings: Today: DS(IJ), Chapter 8; Next topic: Chapter 9.
Last modified: Tue Apr 7 14:20:47 2020 CS61B: Lecture #29 1
Copyright By PowCoder代写 加微信 powcoder
Better than N lg N?
• Can prove that if all you can do to keys is compare them, then sorting must take Ω(N lg N ).
• Basic idea: there are N! possible ways the input data could be scrambled.
• Therefore, your program must be prepared to do N ! different com- binations of data-moving operations.
• Therefore, there must be N! possible combinations of outcomes of all the if-tests in your program, since those determine what move gets moved where (we’re assuming that comparisons are 2-way).
Decision Tree
Height ∝ Sorting time
abc a