Homework #7 COSC 311

//Distributed 3/28/2013		DUE 4/1/2013 
//
//Consider table 8.2 page 435 (duplicated below).
//
//Give sample arrays of size 5, where the data demonstrate best case
//performance and worst case performance for number of exchanges.
//
//
//                # of Comparisons   # of Exchanges
//                Best   Worst       Best   Worst
//Selection sort  O(n^2)  O(n^2)     O(n)   O(n)
//Bubble sort     O(n)    O(n^2)     O(1)   O(n^2)
//Insertion sort  O(n)    O(n^2)     O(n)   O(n^2)

Homework #7 COSC 311

DUE 4/9/2013

Sorting Algorithms comparisons: http://en.wikipedia.org/wiki/Sorting_algorithm

Worst, average, best case: http://en.wikipedia.org/wiki/Worst-case_performance

                
                Best         Worst       
Selection sort  O(n^2)       O(n^2)    
Bubble sort     O(n)         O(n^2)    
Insertion sort  O(n)         O(n^2)    
Quicksort       O(n log n)   O(n^2)
Mergesort       O(n log n)   O(n log n)
Heap sort       O(n log n)   O(n log n)


For bubble sort, insertion sort, and quicksort, best case behavior and worst
case behavior have notably different Big Oh behavior.

For each of the three, give an example of data that will exhibit the best case 
performance and the worst case performance (six examples of data sets in total).

                  Best case data                      Worst case data
Bubble sort

Insertion sort

Quick sort