// header files
#include <iostream>
#include <cmath>

using namespace std;

// global constants
const int ROUTINE_SUCCESS = 0;
const int MAX_N = 25;
const int ARR_INIT_VAL = -1;
const char SPACE = ' ';

// prototypes - primary functions
void generateData( int intArr[], int N );
void selectionSort( int intArr[], int N );

// prototypes - utility functions
void displayArrayStatus( int lIndex, int rIndex, int intArr[], int N );
void initializeArray( int intArr[], int initVal, int N );
int findSmallest( int lIndex, int hIndex, int intArr[] );
bool hasDuplicate( int testVal, int intArr[], int N );
void outputArray( int intArr[], int N );
int promptForInteger( char prompt[] );
void swap( int &one, int &other );

// program
int main()
   {
    // initialize function
    int items[ MAX_N ];
    int numItems;

    // initialize random number generator
    srand( time( NULL ) );

    // initialize array
    initializeArray( items, ARR_INIT_VAL, MAX_N );
    
    // get number of items from user & protect limit
    numItems = promptForInteger( "Enter number of items to sort: " );

    if( numItems > MAX_N )
       {
        numItems = MAX_N;
       }

    // create data
    generateData( items, numItems );

    // output unsorted data
    cout << endl << "Unsorted list of numbers: " << endl;
    outputArray( items, numItems );

    // sort data - bubble sort
    selectionSort( items, numItems );
    
    // output sorted data
    cout << endl << "Sorted list of numbers: " << endl;
    outputArray( items, numItems );

    // end program
    cout << endl;
    system( "pause" );
    return ROUTINE_SUCCESS;
   }

void generateData( int intArr[], int N )
   {
    int newVal, index = 0;

    while( index < N )
       {
        // generate number between 10 & 99
        newVal = rand() % 90 + 10;

        // don't allow duplicate values
        if( !hasDuplicate( newVal, intArr, N ) )
           {
            intArr[ index ] = newVal;
            index++;
           }
       }
   }

void selectionSort( int intArr[], int N )
   {
    int index = 0, smallestIndex;

    while( index < ( N - 1 ) )
       {
        smallestIndex = findSmallest( index, N - 1, intArr );

        displayArrayStatus( index, N - 1, intArr, N );

        swap( intArr[ smallestIndex ], intArr[ index ] );

        index++;
       }
   }

void displayArrayStatus( int lIndex, int rIndex, int intArr[], int N )
   {
    int index = 0;

    rIndex++;

    outputArray( intArr, N );

    N++;

    while( index < N )
       {
        if( ( index == lIndex ) || ( index == rIndex ) )
           {
            cout << "|  ";
           }
        else
           {
            cout << "   ";
           }

        index++;
       }

    cout << endl;

    system( "pause" );
    cout << endl;
   }

void initializeArray( int intArr[], int initVal, int N )
   {
    int index = 0;

    while( index < N )
       {
        intArr[ index ] = initVal;

        index++;
       }
   }

int findSmallest( int lIndex, int hIndex, int intArr[] )
   {
    int smallIndex = lIndex;

    lIndex++;

    while( lIndex <= hIndex )
       {
        if( intArr[ lIndex ] < intArr[ smallIndex ] )
           {
            smallIndex = lIndex;
           }

        lIndex++;
       }

    return smallIndex;
   }

bool hasDuplicate( int testVal, int intArr[], int N )
   {
    int index = 0;

    while( index < N )
       {
        if( testVal == intArr[ index ] )
           {
            return true;
           }

        index++;
       }

    return false;
   }

void outputArray( int intArr[], int N )
   {
    int index = 0;

    while( index < N )
       {
        cout << SPACE << intArr[ index ];
        index++;
       }

    cout << endl;
   }

int promptForInteger( char prompt[] )
   {
    int response;

    cout << prompt;

    cin >> response;

    return response;
   }

void swap( int &one, int &other )
   {
    int temp = one;

    one = other;

    other = temp;
   }