// This program is the core of an example computer science experiment. The
// experiment tests the prediction that Selection Sort will take more time
// as the array it has to sort gets longer. This prediction follows from
// the observation that Selection Sort's two loops each repeat more often
// to sort a longer array, and therefore that the algorithm executes more
// steps to sort longer arrays.
//
// This program encapsulates Selection Sort in a "SortableArray" class,
// which provides convenient ways to initialize an array and display its
// contents, as well as the core sort method. The arrays that this class
// represents are simply arrays of integers. In full detail, the class
// provides the following to its clients:
//
//  o A constructor that takes a single integer, the desired array size,
//      as its parameter. The constructor creates an array of that size,
//      and fills it with integers in descending order (exactly the
//      opposite of the order that the sort produces).
//    Preconditions: The requested size is greater than 0.
//    Postconditions: The array contains the requested number of integers,
//      in decreasing order, or the array's actual size is 0.
//
//  o A destructor.
//
//  o display, a parameterless message that causes a SortableArray to
//      print its contents to standard output. This message has no return
//      value.
//
//  o sort, a parameterless message that causes a SortableArray to sort
//      itself into ascending order. This message has no return value.
//    Postconditions: The array contains the same integers it contained
//      before receiving the "sort" message, but each (except the last)
//      is less than or equal to the one immediately after it in the array.

// History:
//   April 2001 -- Created by Doug Baldwin.

// Copyright (C) 2008 Cengage Learning.




#include <Events.h>            // MacOS-specific header file, declares "TickCount" clock function
#include <iostream>

using namespace std;




// The interface to the SortableArray class:

class SortableArray {

    public:
    
        SortableArray( const int n );
        ~SortableArray( void );
        void display( void ) const;
        void sort( void );
    
    private:
    
        // Internally, a SortableArray maintains an array of integers
        // and a count of how many elements are in that array. The
        // array is dynamically allocated, and so is represented simply
        // by a pointer to its first element.
        
        int* array;
        int size;
};




// The constructor for SortableArrays. This simple allocates the array,
// and fills it with integers in decreasing order.

SortableArray::SortableArray( const int n ) : size(n)
{
    // Create the array:
    
    array = new int[n];
    
    
    // Fill the array with integers in descending order, if it was
    // successfully created. If creation failed, so indicate by setting
    // size to 0:
    
    if ( array != 0 ) { 
        for ( int i = 0; i < n; i++ ) {
            array[i] = n - i;
        }
    }
    else {
        size = 0;
    }
}




// The destructor for SortableArrays. This deallocates the memory used
// by the internal array, if that array appears to have allocated
// successfully.

SortableArray::~SortableArray( void )
{
    if ( array != 0 ) {
        delete[] array;
    }
}




// The "display" method for SortableArrays. This simply loops through
// the array, printing each element.

void SortableArray::display( void ) const
{
    for ( int i = 0; i < size; i++ ) {
        cout << array[i] << endl;
    }
}




// The "sort" method for SortableArrays. This is a completely standard
// selection sort.

void SortableArray::sort( void )
{
    for ( int current = 0; current < size-1; current++ ) {
    
        int minSoFar = current;
        
        for ( int minSeeker = current+1; minSeeker < size; minSeeker++ ) {
        
            if ( array[minSeeker] < array[minSoFar] ) {
                minSoFar = minSeeker;
            }
        }
        
        int temp = array[current];
        array[current] = array[minSoFar];
        array[minSoFar] = temp;
    }
}




// The main program creates several SortableArray objects and measures
// how long each takes to sort itself. Each run of the program works with a
// single array size, defined by "arraySize".

int main() {

    const int arraySize = 32000;            // The size of the arrays to sort.
    const int subjects = 5;                     // The number of arrays to sort.
    
    
    for ( int i = 0; i < subjects; i++ ) {
    
        SortableArray subjectArray( arraySize );
        
        long startTime = TickCount();
        subjectArray.sort();
        long endTime = TickCount();
        long time = endTime - startTime;
        
        cout << "Sorting a " << arraySize << " element array took ";
        cout << time << " 60ths of a second." << endl;
    }   
    
    return 0;
}