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"