sorting:  quicksort and selection sort

............................................................
quicksort

quicksort algorithm, implementation (Slides V-20, V-22)

quicksort component:  partition (Slide V-23)

partition implementation (Slides V-24, V-25)

group exercises
  trace partition code on a sequence of ints:

    6 4 2 9 5 8 1 7 
    partition returns 4
    partitioned array:  5 4 2 1 6 8 9 7 
    
    1 4 3 2 7 9 5 6 
    partition returns 0
    partitioned array:  1 4 3 2 7 9 5 6 
    
    9 7 6 4 1 2 3 4 
    partition returns 7
    partitioned array:  4 7 6 4 1 2 3 9 
    
    5 1 9 6 4 8 7 2 
    partition returns 3
    partitioned array:  4 1 2 5 6 8 7 9 
    (See full trace of this partition below.)
 
  (Full traces are omitted here, but I'll write them up if
  there's enough demand.)

  trace quicksort on the above sequences...

asymptotic time complexity
  worst case, O(n^2) 
  ideally, O(n lg n)
    ideally == good pivot (close to median) chosen

different versions vary w/ choice of pivot
(all still O(n^2) in worst case)
  first element
    bad case:  sorted list
  randomized
  median of three

Unless we say otherwise, we mean quicksort w/ first element
as pivot.

............................................................
selection sort 

overview and implementation (Slide V-43)

asymptotic time complexity
  worst case:  O(n^2)
  best case:  O(n^2) 


............................................................
partition trace example

lo                  hi
   L                 R
5  1  9  6  4  8  7  2

5 is the pivot.  I'll show the array after each while loop
iteration, highlighting swapped elements w/ carets:

lo                  hi
      L              R
5  1  9  6  4  8  7  2

lo                  hi
         L        R
5  1  2  6  4  8  7  9
      ^              ^
lo                  hi
         L     R  
5  1  2  6  4  8  7  9

lo                  hi
         L  R  
5  1  2  6  4  8  7  9

lo                  hi
         R  L  
5  1  2  4  6  8  7  9
         ^  ^

The while loop condition is now false, so we swap the pivot
into place.

lo                  hi
         R  L  
4  1  2  5  6  8  7  9
^        ^

The above is array A's final state, and 3 is returned as the
pivot's index.