///////
//
// Student: Russell Lowke
//     T.F: Francis Crick
// Unit Seven, pencil-and-paper - question 4 [worth 2pts],  7/30/2002
//
//  Show that improved selection sort requires, on average, only 3/4 as many comparisons.
//



Regular selection sort:

( n(n-1) ) / 2  =  ( n^2 - n ) / 2   approx = n^2 / 2

when n = 8,    n^2 / 2  = 32 comparisons


Improved Selection sort:

( n*n*1.5 ) / 4

when n = 8,   ( n*n*1.5 ) / 4 = 24 comparisons


Ratio of comparisons:

24/32 = .75 = 3/4 as many comparisons.




___________



... working ...
n/2
n*1.5/2
n*n*1.5/4