I. brief overview of sorting (HR 12.7-8)
 A. motivating question
------------------------------------------
          SORTING (HR 12.7-8)

          MOTIVATING PROBLEM

Given a random access collection,
arrange them in nondecreasing order.


extern void Sort( int vec[], int size );
  // PRE:  size >= 0
  // && 0..size-1 are legal indexes of vec
  // MODIFIES: vec[0..size-1]
  // POST: vec[0..size-1] contains the
  // same values as vec[0..size-1]<entry>
  // but sorted into nondecreasing order
------------------------------------------
 B. overview
------------------------------------------
          SORTING OVERVIEW

	             Average    Worst case
Techniques	     Time cost  time cost
 A. bubble           O(N^2)     O(N^2)
 B. selection        O(N^2)     O(N^2)
 C. quicksort        O(N log N) O(N^2)


Benchmark	Bubble Selection Quicksort
1000 random	127.4  80.86	 2.52
1000 sorted	0.16   85.2	 1.43

Key insight:
    Divide and conquer
------------------------------------------
 C. N^2 sorting algorithms (HR 12.7)
	How do you sort a hand of playing cards?
  1. straight selection sort
------------------------------------------
      STRAIGHT SELECTION SORT

#include "slctsort.h"
#include "swap.h"

//  Algorithm: straight selection sort

void Sort( int vec[], int vSize )
{
  int maxIndx; // Index of largest
  int bot;     // "False bot" for pass
  int i;
  
  // INV: 
  // 
  // 
  for (bot = vSize-1; bot >= 1; bot--) {
    maxIndx = 0;
    // INV:
    // 
    for (i = 1; i <= bot; i++) {
      if (vec[i] > vec[maxIndx]) {
	maxIndx = i;
      }
    }
    // ASSERT: 
    // 
    swap(vec[bot], vec[maxIndx]);
  }
}
------------------------------------------
	What's the worst case time complexity?
  2. bubble sort (HR p. 576-7)
------------------------------------------
        IMPROVED BUBBLE SORT

// bubsort2.C
#include "bubsort2.h"
#include "swap.h"

//  Algorithm: an improved bubble sort

void Sort( int vec[], int vSize )
{
  int bot;	    // False bot
  int lastSwapIndx; // last swapped
  int i;
  
  bot = vSize - 1;
  // INV: 0 <= bot < vSize
  // && vec[0..size-1] contains the
  // same values as vec[0..size-1]<entry>
  // && vec[bot..size-1] is sorted
  while (bot > 0) {
    lastSwapIndx = 0;
    // INV: 0 <= lastSwapIndx <= i <= bot
    // && no pair in vec[lastSwapIndx..i]
    // is out of order
    for (i = 0; i < bot; i++)
      if (vec[i] > vec[i+1]) {
	swap(vec[i], vec[i+1]);
	lastSwapIndx = i;
      }
    // ASSERT: i == bot && 
    // vec[lastSwapIndx..size-1]
    // is sorted
    bot = lastSwapIndx;
  }
}
------------------------------------------
	What's the worst case time complexity of this?
	What's the best case time?  When does that occur?
II. quicksort (HR 12.8)
 A. divide and conqueor idea
------------------------------------------
         QUICKSORT IDEA

void Quicksort(int vec[],
               int loBound, int hiBound)
{
  IF 0 or 1 items to sort, return;
  IF 2 items to sort, swap if needed
  ELSE {
    partition vec around someSub so that
       vec[loBound..someSub-1]
      are less than all items in 
       vec[someSub..hiBound];
    Quicksort(vec, loBound, someSub-1);
    Quicksort(vec, someSub, hiBound);
  }
}
------------------------------------------
	What if there is only one element less than the pivot?
	when does the recursion stop?
------------------------------------------
	 IMPROVED QUICKSORT

// qsort2.C
#include "qsort2.h"
#include "partition.h"
#include "swap.h"

// Algorithm: improved quicksort

void Quicksort(int vec[],
               int loBound, int hiBound)
{
  if (hiBound-loBound == 1) { // Two items
    if (vec[loBound] > vec[hiBound]) {
      swap(vec[loBound], vec[hiBound]);
    }
    return;
  }

  int someSub = partition(vec, loBound,
			       hiBound);
  
  if (loBound < someSub-1) {
    // 2 or more items in 1st subvec
    Quicksort(vec, loBound, someSub-1);
  }
  
  if (someSub+1 < hiBound) {
    // 2 or more items in 2nd subvec
    Quicksort(vec, someSub+1, hiBound);
  }
}
------------------------------------------
	Assuming someSub is halfway between loBound and hiBound,
		how many times is Quicksort called on input of size N?
 B. partitioning (HR p.581-584)
------------------------------------------
      PARTITIONING IDEA



















// partition.h

extern int partition(int vec[],
               int loBound, int hiBound);
  // PRE: loBound+1 < hiBound
  // (so at least 3 elements present)
  // && loBound..hiBound are
  // legal indexes of vec
  // MODIFIES: vec[loBound..hiBound]
  // POST: vec[loBound..hiBound] contains
  // the same values as
  //  vec[loBound..hiBound]<entry>
  // but each vec[loBound..FCTVAL] <
  // each vec[FCTVAL..hiBound]
------------------------------------------
------------------------------------------
// partition.C
#include "partition.h"
#include "swap.h"

int partition(int vec[],
               int loBound, int hiBound) 
{
  // ASSERT: there are 3 or more items
  int pivot = vec[(loBound+hiBound)/2];
  vec[(loBound+hiBound)/2] = vec[loBound];
  vec[loBound] = pivot;
  int loSwap = loBound + 1;
  int hiSwap = hiBound;
  do {
    while (loSwap <= hiSwap
	   && vec[loSwap] <= pivot) {
      loSwap++;
    }
    // ASSERT: loSwap <= hiSwap+1
    // && all vec[loBound+1..loSwap-1]
    // are <= pivot && (loSwap < hiSwap)
    // --> vec[lowSwap] > pivot

    while (vec[hiSwap] > pivot) {
      hiSwap--;
    }
    // ASSERT: 
    // 

    if (loSwap < hiSwap) {
      swap(vec[loSwap], vec[hiSwap]);
    }
    // INV: vec[loBound..loSwap-1] <=pivot
    // && vec[hiSwap+1..hiBound] > pivot
    // && (loSwap < hiSwap) -->
    //  vec[loSwap] <= pivot < vec[hiSwap]
    // && (loSwap >= hiSwap) -->
    //  vec[hiSwap] <= pivot
    // && loBound <= loSwap <= hiSwap+1
    // && hiSwap+1 <= hiBound+1
  } while (loSwap < hiSwap);
  vec[loBound] = vec[hiSwap];
  vec[hiSwap] = pivot;
  return hiSwap;
}
------------------------------------------
 C. analysis of quicksort (HR p. 587ff)
III. summary of sorting
 A. summary
------------------------------------------
           SORTING SUMMARY

	             Average  
Techniques	     Time cost
 A. bubble           O(N^2)   
 B. selection        O(N^2)   
 C. quicksort        O(N log N)


Benchmark	Bubble Selection Quicksort
1000 random	127.4  80.86	 2.52

Key insight:
    Divide and conquer
------------------------------------------
 B. radix sort (HR 12.10) (omit)