/**
 * insertionsort.cpp
 * 30apr07/sklar
 *
 * this program demonstrates the insertion sort algorithm.
 *
 */


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


// declare constants
const int NUM_DICE = 5;

// declare global variable
int dice[NUM_DICE];

// declare function prototypes
void initDice();
void printDice( int d[], int n );
void insertionSort();



/**
 * 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()


/**
 * insertionSort()
 *
 * this function performs "insertion" sort, using an auxiliary array.
 *
 */
void insertionSort() {
  int aux[NUM_DICE];
  int j;
  int num_aux = 0;
  int num_passes = 0;
  for ( int i=0; i<NUM_DICE; i++ ) {
    // find place ("j") for entry "dice[i]" in "aux" array
    j = 0;
    while (( j < num_aux ) && ( dice[i] > aux[j] )) {
      j++;
    } // end while
    // shift entries in "aux" array to make room for new entry
    // (if necessary, i.e., if j < num_aux)
    for ( int k=num_aux; k>j; k-- ) {
      aux[k] = aux[k-1];
    } // end for k
    aux[j] = dice[i];
    num_aux++;
    num_passes++;
    cout << "after pass #" << num_passes << ": ";
    printDice( aux, num_aux );
  } // end for j
  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 insertionSort()



/**
 * 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 insertion sort
  insertionSort();

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

} // end of main()