/* Filename:  qsort.cpp

   Author:  Br. David Carlson

   Date:  September 23, 1998

   This file contains the implementations of the QuickSort and Partition
   functions defined in qsort.h.
*/

#include "qsort.h"


/* Given:  First    An integer.
           Second   An integer.
   Task:   To swap the values in these two integers.
   Return: First    Updated integer.
           Second   Updated integer.
*/
inline void Swap(int & First, int & Second)
   {
   int Temp;

   Temp = First;
   First = Second;
   Second = Temp;
   }


/* Given:  NumArray  Array of ints.
           Lower     An index into the array.
           Upper     An index into the array.
   Task:   To quicksort the section of the array from index Lower to Upper.
   Return: NumArray  The sorted array.
*/
void QuickSort(IntArray NumArray, int Lower, int Upper)
   {
   int PivotIndex;

   if (Lower < Upper)
      {
      PivotIndex = Partition(NumArray, Lower, Upper);
      QuickSort(NumArray, Lower, PivotIndex - 1);   // sort left side
      QuickSort(NumArray, PivotIndex + 1, Upper);   // sort right side
      }
   }


/* Given:  NumArray  Array of ints.
           Lower     An index into the array.
           Upper     An index into the array.
   Assume: Lower < Upper
   Task:   To partition the section of NumArray between index Lower and
           index Upper so that everything to the left of the returned
           index is less or equal to the pivot item, NumArray[Lower],
           everything to the right of the returned index is greater
           than the pivot item, and the pivot item itself is located
           at the returned index.
   Return: NumArray  The partitioned array.
           In the function name it returns the index of the pivot value.
*/
int Partition(IntArray NumArray, int Lower, int Upper)
   {
   int Pivot, Left, Right;

   Pivot = NumArray[Lower];
   Left = Lower;
   Right = Upper;

   while (Left < Right)
      {
      // scan from left, skipping items that belong there
      while ((NumArray[Left] <= Pivot) && (Left < Upper))
         Left++;
      // scan from right, skipping items that belong there
      while (NumArray[Right] > Pivot)
         Right--;
      if (Left < Right)
         Swap(NumArray[Left], NumArray[Right]);
      }

   NumArray[Lower] = NumArray[Right];
   NumArray[Right] = Pivot;
   return Right;  // return the pivot index
   }