program Sorts(input, output);
type
  tDate = packed array[1..8] of char;
  rDate = record
    day, month, year : integer;
  end;
  sName = packed array[1..30] of char;
  tSequence = array[1..100] of tDate;
  pSort = procedure (var Seq : tSequence; Num : integer);
var
  sumOfComparisons : integer;
  sumOfSwaps : integer;
  vectorOfSeqSize : array[1..5] of integer;
  X, Y : tSequence;
  i : integer;

{ Процедура Parse Date - разбор строки даты
*
*   Принимает дату и структуру даты, в которую записывает
* результ разбора строки даты.
*
}
procedure ParseDate(var date : tDate; var rd : rDate);
var
  i, s : integer;
  b : boolean;
begin
  with rd do
  begin
    i := 1;
    day := -1;
    month := -1;
    year := -1;
    repeat
      s := 0;
      b := true;
      while b do
      begin
        s := s*10 + (ord(date[i]) - ord('0'));
        i := i + 1;
        b := (i <= 8);
        if b then
          b := (date[i] <> '.');
      end;

      if (day = -1) then
        day := s
      else if (month = -1) then
        month := s
      else if (year = -1) then
        if (s >= 50) then
          year := 1900 + s
        else
          year := 2000 + s;

      i := i + 1;
    until ((i > 8) or ((day <> -1) and (month <> -1) and (year <> -1)));
  end;
end;

{ Функция Date Compare - Сравнение дат
*
*   Возвращает:
*     true  - тогда, когда date1 > date2;
*     false - в иных случаях.
*
}
function CompareDate(var date1 : tDate; var date2 : tDate) : boolean;
var
  d1, d2 : rDate;
begin
  ParseDate(date1, d1);
  ParseDate(date2, d2);
  CompareDate := (d1.year > d2.year) or
                 ((d1.year = d2.year) and (d1.month > d2.month)) or
                 ((d1.year = d2.year) and (d1.month = d2.month) and
                  (d1.day > d2.day));
  sumOfComparisons := sumOfComparisons + 1;
end;

{ Процедура Synthesize Date - создание даты
*
*   Принимает строку даты (куда будет помещён результат) и
* структуру даты.
*
}
procedure SynthesizeDate(var date : tDate; rd : rDate);
var
  i : integer;
procedure PutDateIn(val : integer; var n : integer; leadsnil : boolean);
begin
  if (val >= 10) or leadsnil then
  begin
    date[n] := chr(ord('0') + (val div 10));
    date[n+1] := chr(ord('0') + (val mod 10));
    n := n + 2;
  end
  else
  begin
    date[i] := chr(ord('0') + val);
    n := n + 1;
  end;
end;
begin
  date := '        ';
  i := 1;
  PutDateIn(rd.day, i, true);
  date[i] := '.';
  i := i + 1;
  PutDateIn(rd.month, i, true);
  date[i] := '.';
  i := i + 1;
  PutDateIn(rd.year mod 100, i, true);
end;

{ Функция Days In Month - количество дней в месяце
*
*   Вовзращает число в дней в месяце и году с заданными номерами.
*
}
function DaysInMonth(month, year : integer) : integer;
begin
  case month of
    0,1,3,5,7,8,10,12:
      DaysInMonth := 31;
    4,6,9,11:
      DaysInMonth := 30;
    2:
      if (((year mod 4) = 0) and
          (((year mod 100) <> 0) or ((year mod 400) = 0))) then
        DaysInMonth := 29
      else
        DaysInMonth := 28;
  end;
end;

{ Процедура Normalize Date - нормализация даты
*
*   Проверяет корректность ввёденных числовых занчений в структуре
* даты и если первышает нужные значения, то корректирует дату так,
* чтобы не изменилось фактическое количество дней.
*
}
procedure NormalizeDate(var rd : rDate);
var
  i : integer;
  b : boolean;
begin
  repeat
    b := true;

    if rd.month > 12 then
    begin
      rd.year := rd.year + (rd.month div 12);
      rd.month := rd.month mod 12;
      b := false;
    end;
    if rd.month < 1 then
    begin
      rd.month := abs(rd.month);
      rd.year := rd.year - 1 - (rd.month div 12);
      rd.month := 12 - (rd.month mod 12);
      b := false;
    end;

    i := DaysInMonth(rd.month, rd.year);
    if rd.day > i then
    begin
      rd.month := rd.month + 1;
      rd.day := rd.day - i;
      b := false;
    end
    else if rd.day < 1 then
    begin
      rd.month := rd.month - 1;
      rd.day := rd.day + DaysInMonth(rd.month, rd.year);
      b := false;
    end;
  until b;
end;

{ Процедура Generate Sequence - сгенерировать последовательность
*
*   Генерирует в данном массиве последовательность заданного типа
* заданной длины.
*
*   Параметры:
*   Num  - длина последовательности;
*   Seq  - массив;
*   Tp - тип генерируемой последовательности.
*
}
procedure GenerateSequence(var Seq : tSequence; Num, Tp : integer);
var
  i : integer;
  sd : tDate;
  rd, rds : rDate;
  th : integer;
begin
  { Обнуляем последовательность }
  sd := '01.01.08';
  for i := 1 to 100 do
    Seq[i] := sd;

  { Базовая дата, от которой будем отталкиваться }
  ParseDate(sd, rd);
  rds := rd;
  th := random(60);
  if (random(10) >= 5) then
    th := -th;
  rd.month := rd.month + th;
  rds.month := rd.month - th;
  NormalizeDate(rd);
  NormalizeDate(rds);

  case Tp of
    1:
    begin
      for i := 1 to Num do
      begin
        th := random(random(random(365)));
        rd.day := rd.day + th;
        NormalizeDate(rd);
        SynthesizeDate(sd, rd);
        Seq[i] := sd;
      end;
    end;
    2:
    begin
      for i := 1 to Num do
      begin
        th := random(random(random(365)));
        rd.day := rd.day - th;
        NormalizeDate(rd);
        SynthesizeDate(sd, rd);
        Seq[i] := sd;
      end;
    end;
    3:
    begin
      for i := 1 to Num do
      begin
        th := random(random(random(365)));
        if (odd(i)) then
        begin
          rd.day := rd.day + th;
          NormalizeDate(rd);
          SynthesizeDate(sd, rd);
        end
        else
        begin
          rds.day := rds.day - th;
          NormalizeDate(rds);
          SynthesizeDate(sd, rds);
        end;
        Seq[i] := sd;
      end;
    end;
    4,5:
    begin
      for i := 1 to Num do
      begin
        rd := rds;
        th := random(365*3);
        if random(10) >= 5 then
          th := - th;
        rd.day := rd.day + th;
        NormalizeDate(rd);
        SynthesizeDate(sd, rd);
        Seq[i] := sd;
      end;
    end;
  end;
end;

procedure Swap(var Seq : tSequence; f, t : integer);
var
  d : tDate;
begin
  d := Seq[t];
  Seq[t] := Seq[f];
  Seq[f] := d;
  sumOfSwaps := sumOfSwaps + 1;
end;

procedure SelectionSort(var Seq : tSequence; Num : integer); far;
var
  max, i, j : integer;
begin
  for i := Num downto 2 do
  begin
    max := 1;
    for j :=  2 to i do
      if CompareDate(Seq[j], Seq[max]) then
        max := j;
    if (i <> max) then
      Swap(Seq, i, max);
  end;
end;

procedure QuickSort(var Seq : tSequence; Num : integer); far;
procedure Sort(a, b : integer);
var
  l, r : integer;
  m : tDate;
begin
  m := Seq[random(b-a+1)+a];
  l := a;
  r := b;
  repeat
    while CompareDate(m, Seq[l]) do
      l := l + 1;
    while CompareDate(Seq[r], m) do
      r := r - 1;
    if l <= r then
    begin
     if l < r then
       Swap(Seq, l, r);
     l := l + 1;
     r := r - 1;
    end;
  until l > r;
  if a < r then
    Sort(a, r);
  if l < b then
    Sort(l, b);
end;
begin
  Sort(1, Num);
end;

procedure testSort(fdes : sName; func : pSort);
var
  i, j : integer;
  a : array[1..5,1..2] of integer;
  s : array[1..2] of integer;
begin
  writeln('                 ', fdes, '                 ');
  writeln(' ---------------------------------------------------------------');
  writeln(' |  n  |  параметр   |  номер последовательности  |  среднее   |');
  writeln(' |     |             |    1    2    3    4    5   |  значение  |');
  writeln(' ---------------------------------------------------------------');

  for i := 1 to 4 do
  begin
    s[1] := 0;
    s[2] := 0;
    write(' | ', vectorOfSeqSize[i]:3, ' | сравнения   | ');
    for j := 1 to 5 do
    begin
      GenerateSequence(X, vectorOfSeqSize[i], j);
      sumOfComparisons := 0;
      sumOfSwaps       := 0;
      func(X, vectorOfSeqSize[i]);
      a[j,1] := sumOfComparisons;
      s[1] := s[1] + a[j,1];
      a[j,2] := sumOfSwaps;
      s[2] := s[2] + a[j,2];
    end;
    s[1] := s[1] div 5;
    s[2] := s[2] div 5;
    writeln(a[1,1]:4, ' ', a[2,1]:4, ' ', a[3,1]:4, ' ', a[4,1]:4, ' ',
            a[5,1]:4, '   |   ', s[1]:4, '     |');
    writeln(' |     | перемещения | ',
            a[1,2]:4, ' ', a[2,2]:4, ' ', a[3,2]:4, ' ', a[4,2]:4, ' ',
            a[5,2]:4, '   |   ', s[2]:4, '     |');
    writeln(' ---------------------------------------------------------------');
  end;
end;

begin
  Randomize;
  vectorOfSeqSize[1] := 10;
  vectorOfSeqSize[2] := 20;
  vectorOfSeqSize[3] := 50;
  vectorOfSeqSize[4] := 100;
  vectorOfSeqSize[5] := 200;

  testSort(' Сортировка простым выбором   ', SelectionSort);
  testSort(' Быстрая сортировка (рекурс.) ', QuickSort);

end.