const
	size = 100;
 	randomInt = 30;

type
	A = array [1..size] of Integer;

var
	TMass: A;
	menuInt, menuInt2, N	: Integer; // N - количество элементов

procedure Input(var TMass: A); // Запись массива вручную
var i: Integer;
begin
  writeln('Введите N: ');
  read(N);
  writeln('Введите массив: ');
	for i:= 1 to N do
		readln(TMass[i]);
end;

procedure Output(TMass: A); // Вывод
var i: integer;
begin
	for i:= 1 to N do 
		write(TMass[i],';');
end;

procedure randomGenerate(var TMass: A); // Рандомная последовательность
var a, i: integer;
begin
	writeln('Количество элементов: ');
	read(N);
	randomize;
	for i:=1 to N do begin
		a := random(N);
		TMass[i] := a;
	end;
	writeln('Массив сгенерирован');
end;

procedure BubbleSortv1(var TMass: A); // Пузырьковая сортировка версия 1
var j, i : integer; 
		WasSwap : Boolean;
begin
	for j:=1 to N do begin
		WasSwap := False;
		for i:=1 to N-j do begin
			if TMass[i] > TMass[i+1] then begin
				Swap(TMass[i],TMass[i+1]);
				WasSwap := True;
			end;
		end;
		If WasSwap = False then exit;
	end;
end;

procedure BubbleSortv2(var TMass: A); // Пузырьковая сортировка версия 2
var R, j : integer;
		WasSwap : Boolean;
begin
	R:=N;
	WasSwap:=True;
	while (R>1) and WasSwap do begin
		WasSwap := False;
		for j:=1 to R-1 do
			if TMass[j] > TMass[j+1] then begin
				Swap(TMass[j], TMass[j+1]);
				WasSwap:=True;
			end;
			Dec(R);
	end;
end;

procedure InsertionSort(var TMass: A); // Простые вставки
var i, j, R : integer;
begin
	for i := 2 to N do begin // 
		R := TMass[i];
		j := i - 1; // левая граница
		while (R < TMass[j]) and (j > 0) do begin
			TMass[j+1] := TMass[j];
			Dec(j);
		end;
		TMass[j+1] := R;
	end;
end;

procedure FastSort(var TMass: A; L, R: Integer); // Быстрая сортировка
var i, j, medium: integer;
begin
	i := L;
	j := R;
	medium := TMass[(L+R) div 2];
	repeat
		while TMass[i] < medium do Inc(i); // i увел-ем до тех пор, пока i-ый элемент не окажется больше опорного(расширяем левую часть)
		while medium < TMass[j] do Dec(j); // j уменьшаем до тех пор, пока  j-ый элемент не окажется меньше опорного(сокращаем правую часть)
		if i <= j then begin
			if TMass[i] > TMass[j] then begin
			  Swap(TMass[i], TMass[j]);
			  Inc(i);
			  Inc(j);
			end;
		end;
	until i>j;
	if L<j then FastSort(TMass, L, j); // Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента
	if i<R then FastSort(TMass, i, R);
end;

procedure Menu(); // Меню 
var L, R :integer;
begin
  writeln('Выберите метод заполнения'#10'№1.Ручной метод'#10'№2.Случайно сгенерированный');
	readln(menuInt); // Выполнение меню
	case menuInt of
		1: Input(TMass);
		2: randomGenerate(TMass);
	end;
	writeln('Выберите сортировку'#10'№1.Пузырёк'#10'№2.Простые вставки'#10'№3.Быстрая сортировка'#10);
	readln(menuInt2);
	case menuInt2 of 
		1 : BubbleSortv1(TMass); // Пузырек
		2 : InsertionSort(TMass); // Вставки
		3 : FastSort(TMass, L, R); // Быстрая сортировка
	end;
end;

begin // Тело программы
	Menu();
	Output(TMass);
end.