program tris;

	const

{ pour definir la position de la fenetre sur l'ecran }
		LEFT = 10;
		RIGHT = 630;
		TOP = 40;
		BOTTOM = 390;

{ limites dans lesquelles peuvent etre affiches les points }
		X_MIN = 0;
		X_MAX = RIGHT - LEFT - 16;
		Y_MIN = 0;
		Y_MAX = BOTTOM - TOP - 16;

		N_ALGO = 4;											{ nombre d'algorithmes de tri								}
		A_SEL = 1;											{ tri par selection											}
		A_QCK = 2;											{ quicksort													}
		A_INS = 3;											{ tri par insertion											}
		A_BUL = 4;											{ tri a bulles													}

		N = 150;												{ nombre d'elements a trier									}
		N_SWAP = N + 1;
		N_COMP = N + 2;
		V_SIZE = (Y_MAX - Y_MIN) div N_ALGO;			{ taille de la portion de fenetre attribuee a un algo		}
		T_SIZE = 10;											{ hauteur du titre de l'algorithme							}
		H_SIZE = 100;
		WIDTH = (X_MAX - X_MIN) div N;					{ longueur + 1 du cote du carre representant un element	}
		MAX = (V_SIZE - T_SIZE) div WIDTH - 1;			{ valeur maximale d'un element : 0 <= t[i] <= MAX		}
		TEMPO = 5000;										{ temporisation dans la procedure wait						}

		N_OP = 500;

	type
		ptr = ^op;
		op = record
				ij: array[1..N_OP] of integer;
				next: ptr;
			end;

	var
		t: array[1..N_ALGO, 0..N_COMP] of integer;	{ tableau des elements a trier (avec sentinelle)			}
		rec: array[1..N_ALGO] of ptr;
		index: array[1..N_ALGO] of integer;
		randSeed0: LongInt;


{ procedure affichant une fenetre sur l'ecran : }

	procedure open_window;
		var
			r: Rect;
			i: integer;
	begin
		SetRect(r, LEFT, TOP, RIGHT, BOTTOM);		{ remplit les champs du record avec les valeurs donnees	}
		SetDrawingRect(r);								{ fixe la taille de la fenetre graphique						}
		ShowDrawing;									{ affiche la fenetre graphique								}
		SetRect(r, X_MIN, Y_MIN, X_MAX, Y_MAX);
		EraseRect(r);
		for i := 1 to N_ALGO - 1 do					{ trace les lignes separant les algorithmes					}
			begin
				MoveTo(X_MIN, Y_MAX - i * V_SIZE);
				LineTo(X_MAX, Y_MAX - i * V_SIZE);
			end;
		MoveTo(X_MIN, Y_MAX - A_BUL * V_SIZE + T_SIZE);
		WriteDraw(' Tri ˆ bulles');
		MoveTo(X_MIN, Y_MAX - A_INS * V_SIZE + T_SIZE);
		WriteDraw(' Tri par insertion');
		MoveTo(X_MIN, Y_MAX - A_QCK * V_SIZE + T_SIZE);
		WriteDraw(' Quicksort');
		MoveTo(X_MIN, Y_MAX - A_SEL * V_SIZE + T_SIZE);
		WriteDraw(' Tri par sŽlection');
	end;


{ procedure affichant un carre representant un point : }

	procedure plot (algo, i: integer);
		var
			y: integer;
			r: Rect;
	begin
		r.left := X_MIN + (i - 1) * WIDTH;			{ on peut bien sur utiliser la fonction SetRect...	}
		r.top := (Y_MAX - (algo - 1) * V_SIZE - 1) - (t[algo, i] + 1) * WIDTH + 1;
		r.right := r.left + WIDTH - 1;
		r.bottom := r.top + WIDTH - 1;
		InvertRect(r);
	end;


{ procedure effacant un retangle representant un point : }

	procedure erase (algo, i: integer);
	begin
		plot(algo, i);	{ meme procedure car inversion video ! }
	end;


{ procedure attendant soit un clique, soit le temps d'une	}
{ boucle si le bouton de la souris etait deja appuye :		}

	procedure wait;
		var
			i: integer;
	begin
		if not Button then
			begin
				while not Button do
					;
				i := 1;
				while Button and (i < TEMPO) do
					i := i + 1;
			end
		else
			for i := 1 to TEMPO do
				;
	end;


{ procedure affichant les nombres d'echanges et de comparaisons : }

	procedure show_result (algo: integer);
	begin
		MoveTo(X_MIN + H_SIZE, Y_MAX - algo * V_SIZE + T_SIZE);
		WriteDraw('Žchanges : ', t[algo, N_SWAP] : 5, '      comparaisons : ', t[algo, N_COMP] : 5);
	end;


{ procedure initialisant aleatoirement le tableau : }

	procedure init_array;
		var
			i, algo, v: integer;
	begin
		for i := 1 to N do
			begin
				v := round(abs(random) / maxint * MAX);
				for algo := 1 to N_ALGO do
					begin
						t[algo, i] := v;
					end;
			end;
	end;

	procedure show_array;
		var
			i, algo: integer;
	begin
		for i := 1 to N do
			for algo := 1 to N_ALGO do
				plot(algo, i);
	end;

	procedure init_all;
		var
			algo: integer;
	begin
		randSeed0 := TickCount;								{ initialise le generateur de nombre aleatoire	}
		randSeed := randSeed0;
		for algo := 1 to N_ALGO do						{ sentinelle										}
			begin
				t[algo, 0] := -maxint;
				t[algo, N_SWAP] := 0;
				t[algo, N_COMP] := 0;
				rec[algo] := nil;
				index[algo] := 0;
			end;
		init_array;
		show_array;
	end;


	procedure store (algo, i, j: integer; swap_flg: boolean);
		var
			p: ptr;
			k: integer;
	begin
		k := index[algo];
		if (k = 0) then
			begin
				new(p);
				p^.next := rec[algo];
				rec[algo] := p;
				k := 1;
			end
		else
			p := rec[algo];
		if swap_flg then
			p^.ij[k] := (i - 1) * N + j - 1
		else
			p^.ij[k] := -1;
		index[algo] := (k + 1) mod N_OP;
	end;


	procedure swap2 (algo, i, j: integer);
		var
			temp: integer;
			p: ptr;
	begin
		erase(algo, i);
		erase(algo, j);
		temp := t[algo, i];
		t[algo, i] := t[algo, j];
		t[algo, j] := temp;
		plot(algo, i);
		plot(algo, j);
		t[algo, N_SWAP] := t[algo, N_SWAP] + 1;
	end;


	procedure play;
		var
			p, q, r: ptr;
			algo, i, a, b, v: integer;
			fini: boolean;
			a_rect: Rect;
	begin
		randSeed := randSeed0;
		init_array;
		for algo := 1 to N_ALGO do
			show_result(algo);
		for algo := 1 to N_ALGO do
			begin
				p := nil;
				q := rec[algo];
				while q <> nil do
					begin
						r := q^.next;
						q^.next := p;
						p := q;
						q := r;
					end;
				rec[algo] := p;
			end;
		i := 1;
		repeat
			fini := true;
			for algo := 1 to N_ALGO do
				begin
					if (rec[algo] <> nil) then
						begin
							v := rec[algo]^.ij[i];
							if v >= 0 then
								begin
									a := v div N + 1;
									b := v - (a - 1) * N + 1;
									swap2(algo, a, b);
								end;
							if (rec[algo]^.next = nil) then
								begin
									if ((i + 1) mod N_OP = index[algo]) then
										rec[algo] := nil;
								end;
							fini := fini and (rec[algo] = nil);
						end;
				end;
			i := (i + 1) mod N_OP;
			if i = 0 then
				begin
					for algo := 1 to N_ALGO do
						if (rec[algo] <> nil) then
							rec[algo] := rec[algo]^.next;
					i := 1;
				end;
		until fini;
	end;


{ procedure echangeant deux elements : }

	procedure swap (algo, i, j: integer);
		var
			temp: integer;
			p: ptr;
	begin
		temp := t[algo, i];
		t[algo, i] := t[algo, j];
		t[algo, j] := temp;
		t[algo, N_SWAP] := t[algo, N_SWAP] + 1;
		store(algo, i, j, true);
	end;


{ fonction indiquant si un element est plus grand qu'un autre : }

	function compare (algo, a, b: integer): boolean;
	begin
		t[algo, N_COMP] := t[algo, N_COMP] + 1;
		store(algo, a, b, false);
		compare := (a > b);
	end;


{ procedure de tri par selection : }

	procedure tri_selection;
		var
			i, j, m, temp: integer;
	begin
		if N > 1 then
			for i := 1 to N - 1 do
				begin
					m := i;
					for j := i + 1 to N do
						if compare(A_SEL, t[A_SEL, m], t[A_SEL, j]) then
							m := j;
					if m <> i then
						swap(A_SEL, i, m);
				end;
	end;


{ procedure de tri par insertion : }

	procedure tri_insertion;
		var
			i, j, v: integer;
	begin
		if N > 1 then
			begin
				for i := 2 to N do
					begin
						v := t[A_INS, i];
						j := i;
						while (j > 1) and (compare(A_INS, t[A_INS, j - 1], v)) do
							begin
								swap(A_INS, j, j - 1);
								j := j - 1;
							end;
					end;
			end;
	end;


{ procedure de tri a bulles : }

	procedure tri_bulles;
		var
			i, j: integer;
	begin
		if N > 1 then
			for i := N downto 2 do
				for j := 1 to i - 1 do
					if compare(A_BUL, t[A_BUL, j], t[A_BUL, j + 1]) then
						swap(A_BUL, j, j + 1);
	end;


{ procedure de tri par quicksort : }

	procedure quicksort (g, d: integer);
		var
			i, j, v, x: integer;
	begin
		if g < d then
			begin
				i := g;
				j := d;
				v := t[A_QCK, (g + d) div 2];
				repeat
					while compare(A_QCK, v, t[A_QCK, i]) do
						i := i + 1;
					while compare(A_QCK, t[A_QCK, j], v) do
						j := j - 1;
					if i <= j then
						begin
							swap(A_QCK, i, j);
							i := i + 1;
							j := j - 1;
						end;
				until j < i;
				if g < j then
					quicksort(g, j);
				if i < d then
					quicksort(i, d);
			end;
	end;


begin
	open_window;
	init_all;
	tri_bulles;
	show_result(A_BUL);
	tri_insertion;
	show_result(A_INS);
	quicksort(1, N);
	show_result(A_QCK);
	tri_selection;
	show_result(A_SEL);
	play;
end.