//////////////////////////////////////////////////////////////////////
//
//	sorts.cpp
//
//	Started by Jeff Ondich on 5/11/98
//	Last modified 5/11/98
//
//	This program illustrates sorting.
//
//	The main program generates a list of numbers
//	to sort, prints them, sorts them, and then
//	prints the sorted list so we can make sure the
//	sorting is working.
//
//	Try a few experiments.
//	
//	1.	Compile and run the program.  Run it a few
//		more times to see that we are getting a
//		different shuffled list each time.  If
//		you comment out the "srand(...)" line,
//		recompile, and run it a few more times
//		again, what happens?
//
//	2.	The main program calls InsertionSort at the
//		moment.  Replace the InsertionSort call with
//		a SelectionSort call to see that SelectionSort
//		is working properly.
//
//	3.	What do you have to change in InsertionSort
//		to make it sort in decreasing order instead
//		of increasing order?  How about SelectionSort?
//
//	4.	Try timing the program.  First, change kArraySize
//		to 5000 and comment out the calls to PrintNumbers
//		(you won't want to see that the program has
//		indeed sorted the 5000 numbers).  Recompile and then
//		run the program like this:
//
//			time sorts
//
//		which will give you output that looks something like:
//
//			4.5u 0.0s 0:04 94% 0+0k 0+0io 0pf+0w
//		
//		This tells you that "sorts" took approximately 4.5
//		seconds of CPU time, and approximately 0:04 of
//		actual time.  The "system" time referred to by 0.0s
//		is not relevant for this program.
//
//	5.	Change kArraySize to 10000, and time the resulting
//		program.  Try 15000 and 20000, too.  Do you see a
//		pattern in the relationship between array sizes
//		and times?  We'll talk about this relationship
//		in class.
//
//////////////////////////////////////////////////////////////////////

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

const int kArraySize = 12;

// Function prototypes.

void Shuffle( int a[], int N );
void PrintNumbers( int a[], int N );
void SelectionSort( int a[], int N );
void InsertionSort( int a[], int N );
void RecSelectionSort( int a[], int N );
void MergeSort( int a[], int N );


int comparisonCount;

////////////////////////////////////////////////////////
//
//	The main program.  Generate a random permutation,
//	print it, sort it, and print again.
//
////////////////////////////////////////////////////////

int main( void )
{
	// "Seed" the standard C/C++ random number generator.
	// The time() function lets us provide a seed that
	// depends on the time--that is, we get different
	// random numbers whenever we run the program.

	srand( (int)time(NULL) );


	int		myNumbers[kArraySize];

	Shuffle( myNumbers, kArraySize );
//	PrintNumbers( myNumbers, kArraySize );

	comparisonCount = 0;
	SelectionSort( myNumbers, kArraySize );
//	MergeSort( myNumbers, kArraySize );
//	PrintNumbers( myNumbers, kArraySize );
	
	cout << "Comparisons: " << comparisonCount << endl;

	return( 0 );
}

////////////////////////////////////////////////////////
//
//	Shuffle generates a pseudo-random permutation of N
//	integers.  See p. 139 of "Seminumerical Algorithms,
//	2nd edition,"  by Donald Knuth, for more details.
//
////////////////////////////////////////////////////////

void Shuffle( int a[], int N )
{
	int		i, swapIndex, temp;

	for( i=0; i < N; i++ )
		a[i] = i;
	
	for( i=N-1; i > 0; i-- )
	{
		swapIndex = rand() % (i+1);
		temp = a[i];
		a[i] = a[swapIndex];
		a[swapIndex] = temp;
	}
}


////////////////////////////////////////////////////////
//
//	PrintList prints out the first N elements of the
//	given array, on one line & separated by spaces.
//
////////////////////////////////////////////////////////

void PrintNumbers( int a[], int N )
{
	for( int i=0; i < N; i++ )
		cout << a[i] << " ";
	
	cout << endl;
}


////////////////////////////////////////////////////////
//
//	SelectionSort sorts the first N elements of the
//	given array in increasing order, using a selection
//	sort algorithm.
//
////////////////////////////////////////////////////////

void SelectionSort( int a[], int N )
{
	for( int i=0; i < N - 1; i++ )
	{
		// Find the smallest item between index i and index N-1.
		int indexOfMin = i;
		for( int j=i+1; j < N; j++ )
		{
			comparisonCount++;
			if( a[indexOfMin] > a[j] )
				indexOfMin = j;
		}
		
		// Swap the max with a[i].
		int temp = a[i];
		a[i] = a[indexOfMin];
		a[indexOfMin] = temp;
	}
}


////////////////////////////////////////////////////////
//
//	InsertionSort sorts the first N elements of the
//	given array in increasing order, using an insertion
//	sort algorithm.
//
////////////////////////////////////////////////////////

void InsertionSort( int a[], int N )
{
	for( int i=1; i < N; i++ )
	{
		int		j;
		int		temp = a[i];
		for( j=i; j > 0  &&  temp < a[j-1]; j-- )
		{
			a[j] = a[j-1];
		}
		a[j] = temp;
	}
}


////////////////////////////////////////////////////////
//
//	RecSelectionSort sorts the first N elements of the
//	given array in increasing order, using a selection
//	sort algorithm.
//
////////////////////////////////////////////////////////

void RecSelectionSort( int a[], int N )
{
	if( N > 1 )
	{
		// Find the minimum from index 0 to N-1.
	
		int indexOfMax = 0;
		for( int i=1; i < N; i++ )
		{
			if( a[indexOfMax] < a[i] )
				indexOfMax = i;
		}

		
		// Swap the minimum item into slot N-1.
		
		int temp = a[indexOfMax];
		a[indexOfMax] = a[N-1];
		a[N-1] = temp;
		
		
		// Sort slots 0 through N-2

		RecSelectionSort( a, N - 1 );
	}
}


////////////////////////////////////////////////////////
//
//	Merge()
//	MSort()
//	MergeSort()
//
//	MergeSort sorts the first N elements of the
//	given array in increasing order, using a merge
//	sort algorithm.  Note that MergeSort itself just
//	calls the recursive function MSort, which in
//	turn calls both itself and Merge.  Merge is
//	where most of the work gets done.
//
////////////////////////////////////////////////////////

////////////////////////////////////////////////////////
//	Merge  merges two adjacent portions of a given array.
//
//	Preconditions:
//		(1) a[bottom],...,a[middle] are in increasing order
//		(2) a[middle+1],...,a[top] are in increasing order
//		(3) top > middle  and  middle >= bottom
//
//	Postconditions:
//		(1) a[bottom],...,a[top] compose the same set of
//			numbers as before, but now in increasing order
//		(2) The rest of the array a[] is unchanged
////////////////////////////////////////////////////////

void Merge( int a[], int bottom, int middle, int top )
{
	int		temp[kArraySize];
	int		i = bottom;
	int		j = middle + 1;
	int		k = 0;

	// While both lists still have items in them, merge those
	// items into the temporary array temp[].

	while( i <= middle  &&  j <= top )
	{
		if( a[i] < a[j] )
		{
			temp[k] = a[i];
			i++;
		}
		else
		{
			temp[k] = a[j];
			j++;
		}
		k++;
	}
	
	// Once one of the lists has been exhausted, dump the other
	// list into the remainder of temp[].

	if( i > middle )
	{
		while( j <= top )
		{
			temp[k] = a[j];
			j++;
			k++;
		}
	}
	else
	{
		while( i <= middle )
		{
			temp[k] = a[i];
			i++;
			k++;
		}
	}


	// Copy temp[] into the proper portion of a[].

	for( i=bottom; i <= top; i++ )
		a[i] = temp[i-bottom];
}


void MSort( int a[], int bottom, int top )
{
	if( bottom < top )
	{
		int middle = (bottom + top) / 2;
		MSort( a, bottom, middle );
		MSort( a, middle + 1, top );
		Merge( a, bottom, middle, top );
	}
}


void MergeSort( int a[], int N )
{
	MSort( a, 0, N-1 );
}