In this week we will study the QuickSort algorithm in detail, discuss in general terms the RadixSort algorithm, and review all the other sorting algorithms we have covered this year.  Your assignment is to thoroughly understand all of these algorithms as well as the attached code in preparation for a quiz on Tuesday Apr-10.

Good luck.

DK

//////////////////////////////////////////////////
/////  Sort Functions Demonstration Code
/////  by David Kosbie
//////////////////////////////////////////////////

// This program demonstrates the following 7 sorts:
// insertionSort, selectionSort, bubbleSort,
// mergeSort, quickSort, radixSort, and heapSort.

// The IntroCS students are responsible for fully
// understanding all the sorting algorithms, but
// do not need to actually code radixSort.  You must
// also understand how a function (like testSortFunction)
// can take another function (like sortFn) as an argument,
// and in particular you should be able to supply the
// signature to testSortFunction in case it was for some
// reason missing in your quiz (hint, hint...).

// The AP CS students are responsible for all the material.

//////////////////////////////////////////////////
/////  Includes, Typedefs, Constants
//////////////////////////////////////////////////

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <math.h>
#include "apvector.h"

typedef apvector<int> intVector;
typedef intVector& intVectorByReference;
typedef int& intByReference;

const int BASE = 10;
const int MAX_EXPT = 6;

//////////////////////////////////////////////////
/////  loadVector(), printVector(), and swap()
//////////////////////////////////////////////////

// loadVector() loads the vector v with
// random elements in [0,BASE^MAX_EXPT)
// (presently 10^6).
void loadVector(intVectorByReference v)
{
 // load vector with numbers mostly random in [0,BIG_NUM]
 int len = v.length();
 for (int i = 0; i < len; i++)
  v[i] = rand() % int(pow(BASE,MAX_EXPT));
}

// This function is provided here for debugging purposes,
// and is not currently called by any functions below.
void printVector(intVectorByReference v)
{
 // print vector elements separated by two spaces with
 // a carriage return at the end
 for (int i = 0; i < v.length(); i++)
  cout << v[i] << "  ";
 cout << endl;
}

void swap(intByReference x, intByReference y)
{
 int temp;
 temp = x;
 x = y;
 y = temp;
}

//////////////////////////////////////////////////
/////  insertionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly inserts the element at the
// cursor into the sorted vector to the left of the cursor.

void insertionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
 for (cursor=1; cursor<len; cursor++)
  for (i=0;i<cursor;i++)
   if (v[i] > v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  selectionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly finds the smallest element from
// the cursor to the right end of the vector and swaps
// that element with the cursor.

void selectionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
 for (cursor=0; cursor<len-1; cursor++)
  for (i=cursor+1;i<len;i++)
   if (v[i] < v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  bubbleSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly sweeps through the vector and
// swaps each pair of elements which are out of order.
// This is repeated until an entire sweep results in no swaps.

void bubbleSort(intVectorByReference v)
{
 int len, cursor;
 bool unsorted;
 
 len = v.length();
 unsorted = true;
 
 while (unsorted == true)
 {
  unsorted = false;
  for (cursor=1; cursor < len; cursor++)
   if (v[cursor] < v[cursor-1])
   {
    swap(v[cursor],v[cursor-1]);
    unsorted = true;
   }
 }
}

//////////////////////////////////////////////////
/////  mergeSort()
//////////////////////////////////////////////////

// This O(n log n) sort is much faster than the O(n^2) sorts
// above.  It is also recursive whereas the above sorts are
// iterative.  It operates by recursively sorting the left
// and right halves of the vector and then merging the sorted
// halves into a sorted whole.

void merge(intVector& v,int lo,int hi,intVector& mergeVector)
{
 // 1. Declare variables
 int mid, mergeIndex, mergeSize, leftIndex, rightIndex;
 int leftMaxIndex, rightMaxIndex;
 bool leftHalfDone, rightHalfDone;
 
 // 2. Initialize variables
 mid = (hi + lo) / 2;
 leftIndex = lo;
 leftMaxIndex = mid;
 rightIndex = mid+1;
 rightMaxIndex = hi;
 leftHalfDone = false;
 rightHalfDone = false;
 mergeSize = 1 + hi - lo;
 
 // 3. Merge into the mergeVector
 for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
 {
  // Get the next element from either left half or right half,
  // place into mergeVector and advance the appropriate index.
  // Use the left half if:
  //  a)  The right side is done, or
  //  b)  The left side is not done, and the left side is smaller
  if ((rightHalfDone == true) ||
   ((leftHalfDone == false) && (v[leftIndex] < v[rightIndex])))
  {
   // Use the next element on the left half
   mergeVector[mergeIndex] = v[leftIndex];
   leftIndex++;
   if (leftIndex > leftMaxIndex)
    leftHalfDone = true;
  }
  else
  {
   // Use the next element on the right half
   mergeVector[mergeIndex] = v[rightIndex];
   rightIndex++;
   if (rightIndex > rightMaxIndex)
    rightHalfDone = true;
  }
 }
 
 // 4. Copy from mergeVector back into v
 for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
  v[lo + mergeIndex] = mergeVector[mergeIndex];
}

// This function sorts the elements from v[lo] to v[hi].
void mergeSort(intVector& v,int lo,int hi, intVector& mergeVector)
{
 int mid;
 
 // 1 Base Case: if there is 1 (or fewer) elements,
 // then the vector is sorted, so just return.
 if (hi <= lo)
  return;
 
 // 2.  Recursive Case
 mid = (hi + lo) / 2;
 mergeSort(v,lo,mid,mergeVector);   // Sort the left half
 mergeSort(v,mid+1,hi,mergeVector); // Sort the right half
 merge(v,lo,hi,mergeVector);        // And merge the sorted halves
}

void mergeSort(intVectorByReference v)
{
 intVector mergeVector(v.length());
 mergeSort(v,0,v.length()-1,mergeVector);
}

//////////////////////////////////////////////////
/////  quickSort()
//////////////////////////////////////////////////

// This O(n log n) sort is also recursive like mergeSort.
// It is typically about twice as fast as mergeSort.  However,
// while the average performance for quickSort is O(n log n),
// its worst-case performance (if you pick the worst pivot each
// time) is O(n^2).  Conversely, mergeSort's worst-case performance
// is the same as its average-case performance:  both are O(n log n).

// This sort operates by choosing a pivot, then splitting the
// vector so that the elements less than or equal to the pivot
// are to the left of the pivot, and those greater than the
// pivot are to the right of the pivot.  Then the two portions
// to the left and right of the pivot are recursively sorted.

int getPivotIndex(intVectorByReference v,int lo,int hi)
{
 return lo;
}

int pivot(intVectorByReference v, int lo, int hi)
{
 int pivotIndex;
 // 1. get a pivot index and swap it to the first position
 pivotIndex = getPivotIndex(v,lo,hi);
 swap(v[pivotIndex],v[lo]);
 
 // 2. Swap elements as necessary so those less than or
 //    equal to the pivot are in the left portion, and
 //    those greater than the pivot are in the right portion
 //    of the vector.
 int loPointer = lo + 1; // lo is the pivot, and we don't count it
 int hiPointer = hi;
 
 while (loPointer < hiPointer)
 {
  if (v[loPointer] <= v[lo])
   loPointer++;
  else if (v[hiPointer] > v[lo])
   hiPointer--;
  else
   // Both left and right elements are on the wrong
   // side, so swap them and continue.
   swap(v[loPointer],v[hiPointer]);
 }
 
 // 3. Swap the pivot into the new location
 assert(loPointer == hiPointer);
 int newPivotIndex;
 if (v[loPointer] <= v[lo])
  newPivotIndex=loPointer;
 else
  newPivotIndex=loPointer-1;
 swap(v[newPivotIndex],v[lo]);
 return newPivotIndex;
}

void quickSort(intVectorByReference v,int lo, int hi)
{
 if (lo >= hi)
  return;
 
 int p = pivot(v,lo,hi);
 
 quickSort(v,lo,p-1);
 quickSort(v,p+1,hi);
}

void quickSort(intVectorByReference v)
{
 quickSort(v,0,v.length()-1);
}

//////////////////////////////////////////////////
/////  radixSort()
//////////////////////////////////////////////////

// This sort is O(n log RANGE), where RANGE is the range of
// the elements in the vector.  For example, here we are using
// elements from 0 to 999,999, so our range is 10^6, and this
// requires 6 iterations, thus this is O(6 * n), which in fact
// is O(n).

// Thus, for large enough n, this sort will be arbitrarily
// faster than either mergeSort or quickSort (and of course
// will completely bury insertionSort, selectionSort, and bubbleSort).
 

// Here is a revised implementation of radixSort which rather
// than using conventional buckets instead implements the buckets
// as pseudo-linked-lists by storing the "links" as indices
// in vectors.  The bucketVector holds the first index i for each
// bucket, and then the next index for that bucket is stored
// in linkVector[i], terminating when this equals -1.
void radixSort(intVectorByReference v)
{
 int i, expt, divver = 1, modder = 1, bucket, vlen = v.length();
 intVector linkVector(vlen);
 intVector copyVector(vlen);
 intVector bucketVector(BASE);

 for (expt=0; expt < MAX_EXPT; expt++)
 {
  // initialize the bucket vector to all -1's
  for (i=0;i<BASE;i++)
   bucketVector[i] = -1;

  // now place each element of the vector in the
  // appropriate bucket for the expt'th digit
  modder *= BASE;
  divver = modder / BASE;
  for (i=vlen-1;i>=0;i--)
  {
   bucket = (v[i] % modder) / divver;
   linkVector[i] = bucketVector[bucket];
   bucketVector[bucket] = i;
  }

  // next, load the copy vector with the buckets
  int copyIndex = 0;
  for (bucket=0;bucket<BASE;bucket++)
   for (i=bucketVector[bucket];i != -1;i = linkVector[i])
   {
    copyVector[copyIndex] = v[i];
    copyIndex++;
   }

  // finally, copy the copyVector back into the original v
  for (i=0;i<vlen;i++)
   v[i] = copyVector[i];
 }
}

/*

typedef apvector<intVector> intVectorVector;

void radixSort(intVectorByReference v)
{
 intVectorVector buckets(BASE);
 intVector bucketCount(BASE);
 int i, len, bucket, bucketSize;
 len = v.length();
 
 // Initialize buckets
 int defaultBucketSize = 10 + 2 * len / BASE;
 for (i=0;i<BASE;i++)
 {
  bucketCount[i] = 0;
  buckets[i].resize(defaultBucketSize);
 }
 
 // Iterate over each expt up to MAX_EXPT
 int divver, modder = 1;
 for (int expt=0; expt < MAX_EXPT; expt++)
 {
  modder *= BASE;
  divver = modder / BASE;
  // 1.  Place each element v[j] into the approprate bucket
  //     based on the expt'th digit in v[j]
  for (int j=0;j<len;j++)
  {
   bucket = (v[j] % modder) / divver;
   bucketSize = buckets[bucket].length();
   // add v[j] to this bucket now
   // first make sure there is room
   if (bucketCount[bucket] >= bucketSize)
    buckets[bucket].resize(2*bucketSize);
   buckets[bucket][bucketCount[bucket]] = v[j];
   (bucketCount[bucket])++;
  }
 
  // 2.  Copy the buckets, from bucket[0] to bucket[BASE-1],
  //     back into v.
  //     AND clear the buckets for the next iteration by
  //     resetting the bucket count to 0!
  int vIndex = 0;
  for (bucket = 0; bucket < BASE; bucket++)
  {
   for (i=0; i<bucketCount[bucket];i++)
    v[vIndex++] = buckets[bucket][i];
   bucketCount[bucket] = 0;
  }
 }
}
*/

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  Heap Accessors (parent, leftChild, rightChild)
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// These simple functions provide the accessors which
// allow us to view a vector as though it is a binary tree.

int getParentIndex(int index)     { return (index - 1) / 2; }
int getLeftChildIndex(int index)  { return (2*index) + 1; }
int getRightChildIndex(int index) { return (2*index) + 2; }

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  HeapSort
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// As noted at the head of this file, this section
// sorts a vector via the heapsort algorithm, which
// places all the elements of vector in-place into a
// heap (addNodesToHeap), then removes then all in
// order (removeNodesFromHeap), leaving a sorted vector.
// This is done in nlogn (hence, optimal) time.

void addNodesToHeap(intVectorByReference v)
{
 int index, parent, cursor, len = v.length();
 for (cursor = 1; cursor < len; cursor++)
 {
  // add the node at v[cursor] to the heap
  // assuming v[0]...v[cursor-1] are already a heap.
  // Do this by percolating the value at v[cursor]
  // up towards the root until it is either the root
  // itself or its parent is >= to it.
  index = cursor;
  while (index > 0)
  {
   parent = getParentIndex(index);
   if (v[parent] >= v[index])
    // it is in the right place now, so break
    break;
   // it is in the wrong place, so swap and keep going up
   swap(v[parent],v[index]);
   index = parent;
  }
 
 }
}

void removeNodesFromHeap(intVectorByReference v)
{
 int cursor, index, leftChild, rightChild, largerChild;
 for (cursor = v.length()-1;cursor > 0; cursor--)
 {
  // swap the node at v[cursor] with the value at
  // the root -- v[0] -- which also is the largest
  // remaining value in the heap.
  swap(v[0],v[cursor]);
 
  // Now we must reestablish the partially-sorted
  // heap property by percolating the root value
  // down through the larger child at each level until
  // it is either a leaf or is larger than both children.
  index = 0;
  while (true)
  {
   // 1. Get left child, and stop if there isn't one
   leftChild = getLeftChildIndex(index);
   if (leftChild >= cursor)
    // if there is no left child, then we have
    // pushed the value down to a leaf and we're done
    break;
 
   // 2. Get the right child, and determine the larger child
   rightChild = getRightChildIndex(index);
   if ((rightChild >= cursor) ||
    (v[leftChild] >= v[rightChild]))
    largerChild = leftChild;
   else
    largerChild = rightChild;
 
   // 3. Stop if the node is >= the larger child
   if (v[index] >= v[largerChild])
    break;
 
   // 4. It's not, so percolate down and keep going
   swap(v[index],v[largerChild]);
   index = largerChild;
  }
 
 }
}

void heapSort(intVectorByReference v)
{
 addNodesToHeap(v);
 removeNodesFromHeap(v);
}

//////////////////////////////////////////////////
/////  verifySorted() and testSort()
//////////////////////////////////////////////////

void verifySorted(intVectorByReference v)
{
 int cursor;
 for (cursor=v.length()-1; cursor>0; cursor--)
  if (v[cursor] < v[cursor-1])
  {
   cout << "Uh oh -- vector not sorted at index "
    << cursor << endl;
   return;
  }
  cout << "Wahoo -- the vector is sorted!" << endl;
}

// Note:  IntroCS students are *not* responsible
// for any part of the following function.
void testSortFunction(char* name,void(*sortFn)(intVector&v),intVector& v)
{
 intVector v2;
 int time1,time2;
 v2 = v;
 cout << endl << "Starting " << name << ": ";
 cout.flush();
 time1 = clock();;
 sortFn(v2);
 time2 = clock();
 verifySorted(v2);
 cout << "Sort took: " << (time2 - time1)/(double(CLOCKS_PER_SEC)) << " seconds" << endl;
}

//////////////////////////////////////////////////
/////  main()
//////////////////////////////////////////////////

void main()
{
 intVector v;
 int vSize;
 bool useSlowSorts;
 
 useSlowSorts = true;
 while (true)
 {
  cout << "Enter size of vector (0 to toggle slow sorts, <0 to exit): ";
  cin >> vSize;
  if (vSize < 0)
   return;
 
  if (vSize == 0)
  {
   useSlowSorts = !useSlowSorts;
   if (!useSlowSorts)
    cout << "not ";
   cout << "using slow sorts." << endl << endl;
  }
  else
  {
   v.resize(vSize);
   loadVector(v);
   cout << endl << "------------------------------";
   if (useSlowSorts)
   {
    testSortFunction("insertionSort",insertionSort,v);
    testSortFunction("selectionSort",selectionSort,v);
    testSortFunction("bubbleSort",bubbleSort,v);
   }
   testSortFunction("mergeSort",mergeSort,v);
   testSortFunction("quickSort",quickSort,v);
   testSortFunction("heapSort", heapSort,v);
   testSortFunction("radixSort",radixSort,v);
   cout << "------------------------------" << endl << endl;
  }
 }
}