/*********************************************************************
 ***        FILE: insertion_sort.cpp
 ***        DATE: 08/22/2003
 ***      AUTHOR: Daniel Dementiev
 *** DESCRIPTION: This programm illustrates the insertion sort method.
 ***              It can be executed without any parameter and then
 ***              it reads teh integer array to sort from the standard
 ***              input, or you can provide an integer number as
 ***              the program argument. In the last case the program
 ***              will generate a random array of the s[ecified size
 ***              then will sort it.
 *********************************************************************/

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

// #define DEBUG_OUTPUT

// -------------------------------------
// This function prints an integer array
// "data" of the size "N"
// -------------------------------------
void print_array(int data[], int N)
{
	for(int i=0;i<N;i++)
		cout<<setw(4)<<data[i];
	cout<<endl;
}

// -------------------------------------
// This function sorts an integer array
//  "data" of the size "N" using the
//  insertion sort algorithm.
// -------------------------------------
void isort(int data[], int N)
{
	int i, j, s, c;
	for(i=1;i<N;i++){
		s = data[i];
		j = i - 1;
		c = data[j];
		while( c > s ){
			data[j+1] = c;
			j--;
			if( j == -1 ) break;
			c = data[j];
		}
		if( j==-1 || j<i-1 )
			data[j+1] = s;
		#ifdef DEBUG_OUTPUT
		cout<<"After pass #"<<i<<": ";
		print_array(data, N);
		#endif
	}
}

void main(int argc, char *argv[])
{
	int *data;
	int  size;

	if( argc > 1 ){
		size = (size=atoi(argv[1])) ? size : 256;
		cout<<"Generating a random array of "<<size<<" elements ...";
		data = new int[size];
		srand((unsigned)time(NULL));
		for(int i=0;i<size;i++)
			data[i] = rand() % (size*3);
		cout<<"done\n";
	}
	else{
		cout<<"Reading data from teh standard input ...";
		int n = 256;
		int i;

		data = new int[n];
		size = 0;
		while( cin>>i ){
			data[size++] = i;
			if( size == n ){
				n += 128;
				int *tmp = new int[n];
				for(i=0;i<size;i++) tmp[i] = data[i];
				delete data;
				data = tmp;
			}
		}
		cout<<"done\n";
	}

	#ifdef DEBUG_OUTPUT
	cout<<"The original array is: ";
	print_array(data, size);
	#endif

	DWORD runtime = GetTickCount();
	isort(data, size);
	runtime = GetTickCount() - runtime;
	cout<<"Runtime is "<<runtime<<" msec\n";

}