Для челночной сортировки определить количество сравнений и обменов - Turbo Pascal

Формулировка задачи:

Челночная сортировка. Размерность сортируемого массива: n = 10, n = 50, n = 250. Для указанного в задании алгоритма сортировки необходимо составить программу сорти- ровки целочисленного массива. При этом приведенные программы можно упростить, заменив массив из записей типа item массивом целых чисел. Тогда роль поля item.key (или a[i].key) будет выполнять сам элемент массива a[i]. Исходный массив заполняется случайным образом при помощи обра- щения к стандартной функции random(т), возвращающей псевдослучайные числа в диапазоне от 0 до m – 1. Например: for i := 1 to n do a[i] := random(m); При этом всегда будем считать, что m = 100. Помните о том, что до первого использования функции random в программе необходимо один раз 94 вызвать процедуру без параметров randomize (например, сразу после первого begin). В результате выполнения данного задания необходимо получить для каждой из приведенных в задании размерностей массива число обменов, со- вершаемых в процессе сортировки. Для этого необходимо ввести в програм- му целочисленный счетчик (устанавливаемый в 0 в начале работы алгоритма сортировки), который будет увеличиваться на единицу после каждой опера- ции обмена (т.е. операции присваивания, в правой или левой части которой встречается элемент массива a). Поскольку искомая величина будет меняться с каждым пуском программы (т.к. сортируемый массив задается случайным образом), повторите сортировку (для размерности сортируемого массива) 10 раз и выдайте среднее число обменов за 10 сортировок

Решение задачи: «Для челночной сортировки определить количество сравнений и обменов»

Листинг программы

type TElement = Integer;
var CCmp, CXch: Word;
 
procedure ShakerSort(var a: array of TElement; nn: Integer);
  function IsLess(a, b: TElement): Boolean;
  begin
    Inc(CCmp); IsLess:=a<b;
  end;
  procedure Swp(var a, b: TElement);
  var t: TElement;
  begin
    Inc(CXch); t:=a; a:=b; b:=t;
  end;
var
  l, r, n, j: Integer;
  t: TElement;
begin
  l:=0; n:=l; r:=nn-1;
  while l<r do begin
    for j:=l to r-1 do
      if IsLess(a[j+1],a[j]) then begin
        n:=j; Swp(a[j+1],a[j]);
      end;
    r:=n;
    for j:=r downto l+1 do
      if IsLess(a[j],a[j-1]) then begin
        n:=j; Swp(a[j],a[j-1]);
      end;
    l:=n;
  end;
end;
 
const
  nt=10; nm=250; W=6; D=1;
  n: array [0..2] of TElement = (10, 50, nm);
var
  a: array [0..nm-1] of TElement;
  i, j, k: Integer;
begin
  Randomize;
  for i:=Low(n) to High(n) do begin
    CCmp:=0; CXch:=0;
    for j:=1 to nt do begin
      for k:=0 to n[i]-1 do a[k]:=-10+Random(21);
      ShakerSort(a,n[i]);
    end;
    WriteLn('Длина: ',n[i]:4,' Попыток: ',nt,
      ' Средние: обменов ',CXch/nt:W:D,' сравнений ',CCmp/nt:W:D);
  end;
  Write('Нажмите Enter...'); ReadLn;
end.

Объяснение кода листинга программы

Тип элемента, с которым будет работать программа, определяется в строке type TElement = Integer;.
Переменные CCmp и CXch используются для подсчета количества сравнений и обменов соответственно. Их инициализируют как Word, что означает, что они будут 16-битными целыми числами.
Функция IsLess(a, b: TElement): Boolean; используется для сравнения двух элементов a и b. Если a меньше b, функция возвращает True, в противном случае - False. Кроме того, она увеличивает счетчик CCmp на 1.
Процедура Swp(var a, b: TElement) используется для обмена двух элементов a и b. Она увеличивает счетчик CXch на 1.
В основной части программы определены константы nt, nm и W, а также массив n размером 3, содержащий некоторые значения.
Далее определен массив a размером nm, который будет заполняться случайными значениями.
В цикле, который повторяется 3 раза, происходит следующее:
- В каждой итерации цикла случайным образом заполняется массив a и вызывается функция ShakerSort(a, n[i]), которая сортирует этот массив методом перетаскивания.
- После каждой итерации цикла выводится сообщение, содержащее количество сравнений и обменов, которые были сделаны во время сортировки.
В конце программы пользователю предлагается нажать Enter, чтобы закрыть программу.