/*----------------------------------------------------------------------------
FILE NAME:     inserSort.cpp

AUTHOR:        Stefano Basagni

CREATED:       September 2003

DESCRIPTION:   Example of a simple C++ program to test both iterative
               and recursive version of Insertion Sort.

---
Copyright (C) 2004 Stefano Basagni

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

To receive a copy of the GNU General Public License write to
the Free Software Foundation, Inc., 59 Temple Place - Suite
330, Boston, MA 02111-1307, USA.

Stefano Basagni can be contacted at basagni@ece.neu.edu.

----------------------------------------------------------------------------*/
// PREPROCESSOR DIRECTIVES
#include <iostream>
#include <ctime>

using namespace std;

#include <vector>

// PROTOTYPES
// Initialize and array with random integer numbers between lb and ub
void initR( vector< int > &A, int n, int lb, int ub );

// Print an array of integers on the screen
void printArray( vector< int > &A, int n );

// Iterative version of Insertion Sort
void insertionSort( vector< int > &A, int n );

// Recursive version of Insertion Sort
void recInsSort( vector< int > &A, int last );


//---------------------------------------------------------------------
// MAIN
int main() {

  int nn = 10;
  vector< int > AA( nn );  

  initR( AA, nn, 1, 999 );

  cout << "The vector to be sorted is: " << endl;
  printArray( AA, nn );

  insertionSort( AA, nn );

  cout << "The sorted vector is: " << endl;
  printArray( AA, nn );

  vector< int > BB( nn );

  initR( BB, nn, 1000, 1999 );
 
  cout << "The vector to be sorted is: " << endl;
  printArray( BB, nn );

  recInsSort( BB, nn );

  cout << "The vector, sorted recursively, is: " << endl;
  printArray( BB, nn );


  return 0;

}
  

//---------------------------------------------------------------------
// FUNCTION DEFS
//---------------------------------------------------------------------
// Initialize a vector with random integer numbers
void initR( vector< int > &A, int n, int lb, int ub ) {
  srand( time( 0 ) );
  for( int a = 0; a < n ; a++ ) 
	 A[ a ] = lb + rand() %  ( ub - lb );
}


//---------------------------------------------------------------------
// Print an array of n elements 
void printArray( vector< int > &A, int n ) {
  for( int a = 0; a < n; a++ )
    cout << A[ a ] << " ";
  cout << endl;
}


//---------------------------------------------------------------------
// Iterative Insertion Sort
void insertionSort( vector< int > &A, int n ) {
  int i, key;
  for ( int j = 1; j < n; j++ ) {
    key = A[ j ];
    i = j - 1;
    while ( ( i >= 0 ) && ( A[ i ] > key ) ) {
      A[ i + 1 ] = A[ i ];
      i--;
	 }
    A[ i + 1 ] = key;
  }
}


//---------------------------------------------------------------------
// Recursive Insertion Sort
void recInsSort( vector< int > &A, int last ) {
  if ( last > 0 ) {
    recInsSort( A, last - 1 );
    int pos = last - 1;
    while ( pos >= 0 && A[ last ] < A[ pos ] )
      pos--;
      pos++;
      int temp = A[ last ];
      for( int a = last - 1; a >= pos; a-- )
        A[ a + 1 ] = A[ a ];
      A[ pos ] = temp;
  }
}