/**
 * selectionsort.cpp
 * 30apr07/sklar
 *
 * this program demonstrates the selection sort algorithm.
 *
 */


#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;


// declare constants
const int NUM_DICE = 5;
const int NO_DICE = 7;

// declare global variable
int dice[NUM_DICE];

// declare function prototypes
void initDice();
void printDice( int d[], int n );
void swapDice( int a, int b );
int findMin();
void selectionSort();



/**
 * initDice()
 *
 * this function initializes the values in the array of dice to
 * integers between 1 and 6
 *
 */
void initDice() {
  for ( int i=0; i<NUM_DICE; i++ ) {
    dice[i] = ( rand() % 6 ) + 1;
  }
} // end of initDice()


/**
 * printDice()
 *
 * this function prints the values in the array of dice
 *
 */
void printDice( int d[], int n ) {
  int i;
  for ( i=0; i<n-1; i++ ) {
    cout << d[i] << " ";
  }
  cout << d[i] << endl;
} // end of printDice()



/**
 * swapDice()
 *
 * this function swaps two values in the array of dice
 *
 */
void swapDice( int a, int b ) {
  int tmp;
  tmp = dice[a];
  dice[a] = dice[b];
  dice[b] = tmp;
  return;
} // end of swapDice()



/**
 * findMin()
 *
 * this function finds the smallest dice value in the array and returns
 * its index; if there is more than one entry matching the minimum
 * value in the array, then the index returned is the first minimum
 * value encountered
 *
 */
int findMin() {
  int min = 0;
  for ( int i=1; i<NUM_DICE; i++ ) {
    if ( dice[i] < dice[min] ) {
      min = i;
    }
  }
  return( min );
} // end of findMin()



/**
 * selectionSort()
 *
 * this function performs selection sort using an auxiliary array.
 *
 */
void selectionSort() {
  int aux[NUM_DICE];
  int aux_end = 0;
  int num_unsorted = NUM_DICE;
  int num_passes = 0;
  int min;
  while ( num_unsorted > 0 ) {
    min = findMin();
    aux[aux_end] = dice[min];
    aux_end++;
    dice[min] = NO_DICE;
    num_unsorted--;
    num_passes++;
    cout << "after pass #" << num_passes << ": ";
    printDice( aux, aux_end );
  } // end while
  for ( int i=0; i<NUM_DICE; i++ ) {
    dice[i] = aux[i];
  } // end for i
  cout << "TOTAL number of passes = " << num_passes << endl;
} // end of selectionSort()



/**
 * main()
 *
 */
int main() {

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

  // initialize the array of dice
  initDice();

  // print the array before sorting it
  cout << "before sorting:";
  printDice( dice, NUM_DICE );

  // perform selection sort
  selectionSort();

  // print the array after sorting it
  cout << "after sorting:";
  printDice( dice, NUM_DICE );

} // end of main()