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"