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

	sortrandom.p

	This program tests a sorting routine 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 2/19/96

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

#include	<gpc-graphics.h>

program sorttester(input,output);

const	maxIntarraySize = 8;
		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; listLength : integer );
var		i : integer;
begin
	for i := 1 to listLength do
		write( list[i]:4 );
	writeln
end;

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

	Sort doesn't do anything, but it does provide a model
	procedure-header for sorting procedures.

 ==============================================================}
procedure Sort( var list : intarray; listLength : integer );
begin
end;

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

	SelectionSort sorts the given array of integers
	in decreasing order.

 ==============================================================}
procedure SelectionSort( var num : intarray; length : integer );
var		i, j, temp, indexOfMax : integer;
begin
	for i := 1 to length-1 do
	begin
	 { Find the largest item between indices i and length }
		indexOfMax := i;
		for j := i+1 to length do
		begin
			if num[j] > num[indexOfMax] then
				indexOfMax := j
		end;

	 { Swap the max item and num[i] }
		temp := num[i];
		num[i] := num[indexOfMax];
		num[indexOfMax] := temp
	end
end;


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

	BubbleSort sorts the given array of integers
	in decreasing order.

 ==============================================================}
procedure BubbleSort( var num : intarray; length : integer );
var		i, j, temp : integer;
begin
	for i := 1 to length-1 do
	begin
		for j := 1 to length-i do
		begin
			if num[j] < num[j+1] then
			begin
				temp := num[j];
				num[j] := num[j+1];
				num[j+1] := temp
			end
		end
	end
end;


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

	GetNumbers gets a sequence of integers from the user,.

 ==============================================================}
procedure GetNumbers( var num : intarray; var length : integer );
begin
	length := 0;
	while (length < maxIntarraySize) and (not eoln) do
	begin
		length := length + 1;
		read( num[length] )
	end;
	readln
end;



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

	The main program

 ==============================================================}
begin
 { If your program is going to use random numbers,
   you need to "seed" the random number generator at
   the beginning of the program.  You only need to do
   this once. }
	srandom( gettime );


	Shuffle( theNumbers, nNumbers );
	PrintList( theNumbers, nNumbers );
	SelectionSort( theNumbers, nNumbers );
	PrintList( theNumbers, nNumbers )
end.