CSC152 2005F, Class 52: Quadratic Sorting Methods Admin: * Exams due * Final Tuesday 9 a.m. * Basketball Tonight @7:30, Tomorrow at 4:00 * Women's games first Overview: * How do you design a sorting algorithm? * Famous sorting algorithms 1: Selection sort * Famous sorting algorithms 2: Insertion sort * Infamous sorting algorithms 3: Bubble sort * Which is best? * Can we do better? Designing Sorting Algorithms: * Sam suggests : "Try it by hand, and then formalize what you do" * Keith's algorithm: * Find the "smallest" element (books, alphabetically-first author) * Shove it on top * Repeat with remaining elements * Concerns? * Efficiency * Finding the smallest element is O(n) * Moving should be O(1) * There are n times we do this * O(n^2) * Revised analysis * n to find the smallest * n-1 to find the next smallest * n-2 to find the next smallest * ... * n + n-1 + n-2 + ... + 1 = n(n+1)/2 is in O(n^2) * Is "top" the beginning or end? * Key operation: Selecting the smallest value Therefore "Selection Sort" Insertion Sort * Mentally separate your collection into two parts: Sorted and Unsorted * Initially: One sorted thing, the rest unsorted * Repeatedly insert somethi8ng from unsorted into sorted * Running time * Kind of like selection sort * N repetitions * In each repetition, you need to look at N things to find the place * Therefore, O(n^2) * Hmmm ... can't you binary search to find the place? * N repetitions * In each repetition, you spend log_2(N) to find the place * O(1) to insert * Therefore O(nlogn) * Hwoops ... O(n) to insert, since we have to "shift" things over * Really O(n^2) * Because insertion is slow, we might was well use an easier-to-check searching + insertino mechanism + As long as element to left is larger, swap with element to left Some strange combinatorics book writer claims that something called "bubble sort" is even better. * Multiple-'pass' algorithm * On each pass, swap neighboring elements if they are out of order * One pass shoves the largest remaining thing to the end * Bubble sort "feels" like insertion sort - Swap to find place * It also "feels" like selection sort - Moving large elements to end * O(n^2) - n passes, each of which has cost n + Or n + n-1 + n-2 + ... + 1 How do we choose among these three algorithms (if we have to choose one of the three)? * The one that is likely to do the fewest swaps? * Bubble sort probably does the most * Selection sort does the fewest O(n) swaps Parallel bubble sort is pretty fast * Looking ahead: * Can we do better than O(n^2)? * Yes, heapsort is O(nlogn) * Can we do better than O(n)? * Probably not, need to look at each element once. * Can we do better than O(nlogn)? * Thm: Not if your basic operations are "compare" and "swap"