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"