CSC152 2006S, Class 48: Quadratic Sorts Admin: * Exam 3 distributed (due a week from Monday). * Exam 2 returned. Discussion next Tuesday. * Some changes to the schedule. * To take a file and make one word per line tr -cs '[:alpha:]' '\n' < FILE | tr '[A-Z]' '[a-z]' Overview: * Bubble sort, and why not to use it. * Selection sort. * Insertion sort. * Looking ahead: Faster sorts. Bubble sort * Step through the list, swapping A[i] with A[i+1] if in incorrect order * One pass takes O(n) * N passes required * Therefore O(n^2) Problem with analysis: N on first pass N-1 on second pass N-2 on third pass ... What is N + N-1 + N-2 + N-3 + ... + 3 + 2 + 1? Insertion Sort * Insert * In the abstract: Two "lists": One already sorted, one unsorted * Initially: Sorted list is empty, Unsorted list contains all elements * At each step * Remove one element from the unsorted list * Put it in the correct place (according to the comparator) in the sorted list * Running time: N repetitions In each repetition * Step through the elements to find the correct place: O(N) * O(N^2) * Hmmm ... we can find the correct place in O(log_2(n)) using binary search * But then we have to shift everything, which is O(n) For a vector sort| unsorted +---+---+---+---+---+---+ |22 |8 | 13| 16| pi| e | +---+---+---+---+---+---+ sort | unsorted +---+---+---+---+---+---+ | 8| 22| 13| 16| pi| e | +---+---+---+---+---+---+ sort | unsorted +---+---+---+---+---+---+ | 8| 13| 16| 22| pi| e | +---+---+---+---+---+---+ Selection Sort * Key operation: Find the largest value * For n = size-1 to 1 Find the largest value in locations 0 .. n Swap it into location n O(n) repetitions O(n) per repetition O(n^2) Can we do better? * Heapsort O(nlogn) * For each element O(n) Put it into the heap O(log_2(n)) * While elements remain in the heap O(n) Grab the smallest remaining O(log_2(n)) Four sorts. Are they stable? (Stable means that equal values preserve their order) * Bubble sort? As long as you don't swap equal values, it is stable * Insertion sort? As long as the insertion pays attention to original order * Selection sort? As long as you select the rightmost equal thing (at least in the version above) * Heap sort? Not likely; impossible (I think) to guarantee Algorithm design techniques * Dynamic programming (nothing to cache) (no recursion) (probably not) * Divide and conquer: * Merge sort: Divide into first half and second half * Quicksort: Divide into "small stuff" and "large stuff"