{
	selection.p
	
	Started by Jeff Ondich 1/29/96
	Last modified 1/29/96
	
	This program generates a pseudo-random permutation of
	the integers 1, 2, ..., HowManyNumbers, and sorts them using
	selection sort.  If the PrintList() procedure calls in
	the main program are uncommented, the program will print
	both the unsorted list and the sorted list.
	
	This program should be compiled using the "gpcgraphics"
	command, since "gettime," "srandom," and "random" are not
	recognized by gpc itself.  To compile selection.p, producing
	an executable program named "selection," , do this:
	
		gpcgraphics selection selection.p
}

program selection(input,output);

const	HowManyNumbers = 10;

type	IntArray = array[1..HowManyNumbers] of integer;

var		myList : IntArray;


procedure PrintList( var list : IntArray; n : integer );
{ Why do I make "list" a variable parameter?  I don't want
to change the original, after all.  The reason is that I
also don't want to make a copy of a possibly large array
every time I call PrintList().  That would be an unnecessary
waste of memory. }
var		i : integer;
begin
	for i := 1 to n do
		write( list[i]:4 );
	writeln
end;

procedure Shuffle( var list : IntArray; n : integer );
{  Generating a pseudo-random permutation of N integers.
   See p. 139 of "Seminumerical Algorithms, 2nd edition,"
   by Donald Knuth, for more details. }
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;  { end of shuffle }

procedure SelectionSort( var list : IntArray; n : integer );
{ This procedure sorts the given list of n integers into
decreasing order. }
var		i, j, temp, indexOfMax : integer;
begin
	for i := 1 to n - 1 do
	begin
		indexOfMax := i;
		for j := i + 1 to n do
			if list[indexOfMax] < list[j] then
				indexOfMax := j;
		
		temp := list[indexOfMax];
		list[indexOfMax] := list[i];
		list[i] := temp
	end
end;


begin
	srandom(gettime);  { Initialize the random number generator. }

	Shuffle( myList, HowManyNumbers );
	PrintList( myList, HowManyNumbers );
	SelectionSort( myList, HowManyNumbers );
	PrintList( myList, HowManyNumbers )
end.