Подсчитать количество присваиваний и количество сравнений при сортировке - Pascal
Формулировка задачи:
Составить программу, которая для массива, заполненного случайными целыми числами, проводит сортировку по неубыванию методом вставки (включения). Подсчитать количество присваиваний и количество сравнений при сортировке. Для проверки работы метода сортировки следует использовать массив из примера,разобранного в «Методических указаниях», выводя на экран весь массив целиком на каждом походе алгоритма.
Решение задачи: «Подсчитать количество присваиваний и количество сравнений при сортировке»
textual
Листинг программы
const ARRAY_SIZE = 10;
type array_t = array[1..ARRAY_SIZE] of integer;
procedure print( const a: array_t );
var
i: integer;
begin
write('array(',ARRAY_SIZE,'): ');
for i:=1 to ARRAY_SIZE do
write( a[i] :5 );
writeln;
end;
const DEV_MODE = true;
var
a: array_t;
i,j,tmp: integer;
eCount: integer = 0;
aCount: integer = 0;
begin
for i:=1 to ARRAY_SIZE do
a[i] := random(-100 , 100);
print(a);
for j:= 2 to ARRAY_SIZE do begin
eCount := eCount + 1;
aCount := aCount + 1;
tmp := a[j];
i := j - 1;
aCount := aCount + 2;
while (i > 0) and (a[i] > tmp) do begin
if ( i>0 ) then eCount := eCount + 1 else eCount := eCount + 2;
a[i+1] := a[i];
if DEV_MODE then print(a);
i := i - 1;
aCount := aCount + 2;
end;
a[i+1] := tmp;
aCount := aCount + 1;
if DEV_MODE then print(a);
end;
writeln( 'Кол-о сравнений: ',eCount );
writeln( 'Кол-о присваиваний: ',aCount );
print(a);
end.
Объяснение кода листинга программы
- Создается константа ARRAY_SIZE, которая определяет размер массива в 10 элементов.
- Создается тип данных array_t, который представляет собой массив из 10 целых чисел.
- Создается процедура print, которая принимает массив в качестве параметра и выводит его содержимое на экран.
- Создается константа DEV_MODE, которая определяет режим отладки.
- Создается переменная a, которая представляет собой массив из 10 целых чисел.
- Создается счетчик eCount для подсчета количества сравнений и присваиваний.
- Создается счетчик aCount для подсчета количества присваиваний.
- Запускается цикл for, который заполняет массив случайными числами от -100 до 100.
- Выводится массив на экран с помощью процедуры print.
- Запускается второй цикл for, который повторяется для каждого элемента массива, начиная со второго.
- Внутри цикла увеличивается счетчик eCount на единицу каждый раз, когда происходит сравнение двух элементов массива.
- Если текущий элемент больше следующего, то увеличивается счетчик aCount на две, так как происходит присваивание временного значения элемента.
- После завершения внутреннего цикла, значение элемента, который был вставлен в позицию i+1, присваивается обратно в позицию i.
- Выводится количество сравнений на экран.
- Выводится количество присваиваний на экран.
- Выводится массив на экран в последний раз.