{
	Quicksort in Pascal
}

program SortArrayDemo (input, output);

const
	MAXSIZE = 100;			{ large enough for demo purposes }

type
	ArrayType = array [1 .. MAXSIZE] of real;

var
	aa : ArrayType;		{ the array to sort  }
	size : integer;		{ its effective size }

{
	read in an array of real numbers and return the count of the
	number read in.
}

function ReadArray (var a : ArrayType) : integer;

var
	n, i : integer;

begin
	write ('How many numbers? ');
	readln (n);

	for i := 1 to n do begin
		write (i, ' : ');
		readln (a [i]);
	end;
	ReadArray := n;
end;

{
	write the first s numbers in the array a
}

procedure WriteArray (var a : ArrayType; s : integer);

var
	i : integer;

begin
	for i := 1 to s do begin
		writeln (i, ' : ', a [i]:6:2);
	end;
end;

{
	select a pivot value, v, and move the values around
	v is somewhere in the middle, every value to the left
	of v is <= v and every value to the right is >= v

	return the location where v ends up.

	loop invariant:
		bottom + 1 <= left <= right <= top
		a [i] <= v if bottom + 1 <= i < left
		a [i] >= v if right <= i <= top
		unknown if left <= i < right
}

function Split (var a : ArrayType; bottom, top : integer) : integer;

var
	v : real;	{ the pivot value }
	left, right : integer;
	temp : real;

begin
	{ take v from the middle, and swap it into the bottom location }

	v := a [(bottom + top) div 2 ];
	a [(bottom + top) div 2] := a [bottom];

	{ split the remaining values }

	left := bottom + 1;
	right := top + 1;
	while left < right do begin
		if a [left] <= v then begin
			left := left + 1;
		end else begin
			right := right - 1;
			temp := a [right];
			a [right] := a [left];
			a [left] := temp;
		end;
	end;

	{ put v back in the middle }
	a [bottom] := a [left - 1];
	a [left - 1] := v;

	Split := left - 1;
end;

{
	sort the section of the array a from bottom through top
}

procedure QuickSort (var a : ArrayType; bottom, top : integer);

var
	middle : integer;

begin
	if top > bottom then begin
		middle := Split (a, bottom, top);
		QuickSort (a, bottom, middle - 1);
		QuickSort (a, middle + 1, top);
	end;
end;

begin  { main program }
	size := ReadArray (aa);
	QuickSort (aa, 1, size);
	WriteArray (aa, size);
end.