(* pikalajittelu.p SJ 12042000 *)

program pikalajitteluesimerkki;

type ELEMENT = integer;
	 INDEX = integer;

function precedes(a, b : ELEMENT) : boolean;
begin
	precedes := a < b;
end;

procedure partition(var A : ARRAY of ELEMENT; i, j : INDEX; var k : INDEX);
	var temp : ELEMENT;
begin
	temp := A[i];
	while i < j do begin
		while (i < j) and precedes(temp, A[j]) do
			j := j-1;
		A[i] := A[j];
		while (i < j) and (not precedes(temp, A[i])) do
			i := i+1;
		A[j] := A[i]
		end;
	k := i;
	A[k] := temp
end;

procedure quicksort(var A : ARRAY of ELEMENT; i, j : INDEX);
	var k : INDEX;
begin
	if i < j then begin
		partition(A, i, j, k);
		quicksort(A, i, k-1);
		quicksort(A, k+1, j)
	end
end;

procedure kuplalajittelu1(var A : ARRAY of ELEMENT; i, j : INDEX);
	var x, y : INDEX;
		temp : ELEMENT;
begin
	for x := i to j-1 do
		for y := j-1 downto x do
			if precedes(A[y+1], A[y]) then begin
				temp := A[y];
				A[y] := A[y+1];
				A[y+1] := temp;
			end;
end;

		

(* pääohjelma kokeilua varten *)

const N = 10000;
	  M = 1000000;

var taulu : array[0..N-1] of ELEMENT;
	i : integer;

begin

	for i := 0 to N-1 do
		(* taulu[i] := random(M); *)
		taulu[i] := i;
		(* taulu[i] := N-i; *)

(*
	writeln('Alkuperäinen');
	for i := 0 to N-1 do
		write(' ', taulu[i]);
	writeln;
*)
	quicksort(taulu, 0, N-1);
	(* kuplalajittelu(taulu, 0, N-1); *)
(*
	writeln('Lajiteltu');
	for i := 0 to N-1 do
		write(' ', taulu[i]);
	writeln;
*)
end.