Sing, Pray

OUTLINE
==========
Sorting Demos Online
Quicksort
Sorting Comparisons (in Eclipse)
GROUP WORK
Test Review Topics


Quicksort
==========

1. If the number of elementes in S is 0 or 1, then return (base case)
2. Pick any element v in S.  It is called the pivot.

	The pivot divides array elements into two groups:  those smaller than the pivot and those larger than the pivot

3. Partition S - {v} (the remaining elements in S) into two disjoint groups: L = {x element of S - {v}|x<=v} and R = {x element of S - {v}|x>=v} 

	In the partition step every element except the pivot is placed in one of two groups.

4. Return the result of Quicksort(L) followed by v followed by Quicksort(R).

The basic quicksort algorithm is recursive.  Details include choosing the pivot, deciding how to partition, and dealing with duplicates.  Wrong decisions give quadratic running times for a variety of common inputs.

Quicksort is fast because the partitioning step can be performed quickly and in place.

	Best case:  O(N log N)
	Worst case: O(N^2)

Quicksort can be faster than mergesort because the partitioning step can be performed significantly faster than the merging step can (no extra array is necessary and the code is compact and efficient).

Picking the pivot is crucial to good performance.  Usually not a good idea to choose the first or last element as pivot.

The middle element is a reasonable but passive choice.
median-of-three partitioning (median of first, last, and middle)

Quicksort is a classic example of using an analysis to guide program implementation

Counters i and j must stop when an element equal to the pivot is encountered

Quicksort Demos
----------------
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
http://www.bluffton.edu/~nesterd/java/SortingDemo.html


Sorting
----------------
http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
http://tanksoftware.com/tutes/uni/sorting.html


Test Review
-----------------
give big-oh analysis
know how binary search works
know how sorting algorithms work and their big-oh analysis
know how to write a recursive method
give big-oh function that matches empirical results as n increases
Collection basics, including which implementation should be used for various situations
know what the graph of the common big-oh expressions looks like
change the base of a logarithm