COMPSCI 61B Lecture Notes - Lecture 29: Quicksort, Time Complexity, Selection Sort
Document Summary
4 philosophies: randomness: pick a random pivot or shuffle before sorting, smarter pivot selection: calculate or approximate the media. 3: preprocess the array: could analyze array to see if quicksort will be slow. Introspection: switch to a safer sort if recursion goes too deep way to do this though (can"t just check if the array is sorted, almost sorted arrays are almost slow) If the pivot always lands somewhere good , quicksort is (n logn). Bad ordering: array already in sorted order. The second strategy requires care in partitioning code to avoid (n^2) behavior on arrays of duplicates. Philosophy 2a: smarter pivot selection (constant time pivot pick) The resulting quicksort has a family of dangerous inputs that an adversary could easily generate. Philosophy 2b: smarter pivot selection (linear time pivot pick) Could calculate the actual median in linear time. If it exceeds some critical value, switch too mergesort. Selection sort: find the smallest item and put it at the front.
