{==============================================================

	midtermsort.p

	This program tests sorting routines by generating
	a random permutation of the integers between 1 and
	maxIntarraySize and sorting it.  You can get a sense
	of whether your sorting algorithm is working by
	leaving the PrintList calls in the main program
	(of course, I recommend using a small value of
	maxIntarraySize if you print out the lists).  You
	can test timing hypotheses by modifying maxIntarraySize
	and commenting out the PrintList calls.

	We stuck our random-number-generating routines
	(srandom, gettime, and random) in the gpc-graphics
	library, so you need to use the -lgraphics flag 
	when you compile this program.

	Started by Jeff Ondich on 5/6/96
	Last modified 5/28/97

==============================================================}

#include	<gpc-graphics.h>

program sorttester(input,output);

const	maxIntarraySize = 10;
		nNumbers = maxIntarraySize;

type	intarray = array[1..maxIntarraySize] of integer;

var		theNumbers : intarray;

{==============================================================

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

 ==============================================================}
procedure Shuffle( var list : IntArray; N : integer );
var		i, j, temp: integer;
begin
	for i := 1 to N do
		list[i] := i;

	for i := N downto 2 do
	begin
		j :=  (random MOD i) + 1;
		temp := list[j];
		list[j] := list[i];
		list[i] := temp
	end
end;


{==============================================================

	PrintList prints the given list of integers on
	a single line.

 ==============================================================}
procedure PrintList( var list : intarray; N : integer );
var		i : integer;
begin
	for i := 1 to N do
		write( list[i]:4 );
	writeln
end;


{========================================================
	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] contain the same set of
			numbers as before, but now in increasing order
		(2) The rest of the array a[] is unchanged
 ========================================================}
procedure Merge( var a : IntArray; bottom, middle, top : integer );
var		temp : IntArray;
		i, j, k : integer;
begin
	i := bottom;
	j := middle + 1;
	k := 0;

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

	while (i <= middle) and (j <= top) do
	begin
		k := k + 1;
		if a[i] < a[j] then
		begin
			temp[k] := a[i];
			i := i + 1
		end
		else
		begin
			temp[k] := a[j];
			j := j + 1
		end
	end;
	
  { Once one of the lists has been exhausted, dump the other
    list into the remainder of temp[] }

	if i > middle then
	begin
		while j <= top do
		begin
			k := k + 1;
			temp[k] := a[j];
			j := j + 1
		end
	end
	else
	begin
		while i <= middle do
		begin
			k := k + 1;
			temp[k] := a[i];
			i := i + 1
		end
	end;


  { Copy temp[] into the proper portion of a[] }

	for i := bottom to top do
		a[i] := temp[i-bottom+1]
end;



{========================================================
	MergeSort sorts the items a[bottom],...,a[top] into increasing
	order.  Thus, a call of MergeSort( myArray, 1, N ) will sort
	the entire N-element array "myArray".

	Note that the recursion is stopped by the fact that MergeSort
	does nothing with 1-element lists.
 ========================================================}
procedure MergeSort( var a : IntArray; bottom, top : integer );
var		middle : integer;
begin
	if bottom < top then
	begin
		middle := (bottom + top) div 2;
		MergeSort( a, bottom, middle );
		MergeSort( a, middle + 1, top );
		Merge( a, bottom, middle, top );
		{PrintList(a,nNumbers);} {*****}
	end
end;



{==============================================================
	SelectionSort sorts the given array of integers
	in decreasing order.
 ==============================================================}
procedure SelectionSort( var num : intarray; N : integer );
var		i, j, temp, indexOfMin : integer;
begin
	for i := 1 to N-1 do
	begin
		indexOfMin := i;
		for j := i+1 to N do
		begin
			if num[j] < num[indexOfMin] then
				indexOfMin := j
		end;

		temp := num[i];
		num[i] := num[indexOfMin];
		num[indexOfMin] := temp;
		{PrintList(num,N);} {*****}
	end
end;

{==============================================================
	The main program
 ==============================================================}
begin
	srandom( gettime );

	Shuffle( theNumbers, nNumbers );

	{PrintList(theNumbers, nNumbers);} {*****}

	SelectionSort( theNumbers, nNumbers );
	{MergeSort( theNumbers, 1, nNumbers );}
end.