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"