/*
   John W. Clark
   This is the quick sort code we did in class.
   I added the print function and the macro.
 */
#include<iostream.h>

// macro using array and size
#define QUICK_SORT(x,y) quick_sort( x, 0, (y - 1))

void quick_sort( int arr[], int start, int stop );
void swap ( int & x, int & y );
void print( int arr[], int size );

int main()
{
    int arr[7] = { 6,2,3,5,1,4,7 };
    print ( arr, 7 );
    QUICK_SORT( arr, 7 );
    print ( arr, 7 );
    return 0;
}

/* =======================================
   void quick_sort( int arr[], int start, int stop )
   input - an array and the index range to sort
   output -
   return - ( by reference ) the sorted array
   ======================================= */
void quick_sort( int arr[], int start, int stop )
{
    int count = stop - start + 1;
    if ( count == 2 )
    {
        if ( arr[ start ] > arr[ stop ] )
            swap( arr[ start ], arr[ stop ] );
    }
    else if ( count > 2 )
    {
        int mid = count / 2 + start;
        // use the midpoint as the pivot
        swap ( arr[ start] , arr[ mid ] );  // put it on the left
#warning "this quick sort uses a really lousy pivot point"
        int pivot = arr[ start ];
        int l = start + 1;  // left index
        int r = stop;       // right index

        while ( l < r ) // they haven't crossed
        {
            for ( ; arr[l] <= pivot ; ++l );
            for ( ; arr[r] > pivot ; --r );
            if( l < r ) // they haven't crossed
                swap( arr[r], arr[l] );
        }
        // put the pivot into the correct location, which is r
        swap( arr[ start ], arr[ r ] );
        quick_sort( arr, start, r - 1 );
        quick_sort( arr, r + 1, stop );
    }
}

/* =======================================
   void swap ( int & x, int & y )
   input - two integers, passed by reference
   output -
   return - ( by reference ) the integers will trade values
   ======================================= */
void swap ( int & x, int & y )
{
    int tmp = x;
    x = y;
    y = tmp;
}

/* =======================================
   void print( int arr[], int size )
   input - an array and the size of the array
   output - the array to stdout, elements seperated by spaces
   return - none
   ======================================= */
void print( int arr[], int size )
{
    for( int i = 0 ; i < size ; ++i )
        cout << arr[i] << " ";
    cout << endl;
}