Сортировка выбором подсчет обменов - PascalABC.NET
Формулировка задачи:
Добрый день.
Сортировка выбором. Подскажите пожалуйста как подсчитать внешний цикл обменов и число операций обмена??
Из теории нам известно что внешний цикл обменов выполняется n-1 раз. - Вроде как я нашел (если правильно написал алгоритм).
Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). Что именно мне и нужно подсчитать.
Также мне известно что в лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только n-1 элементов, а каждая операция обмена требует три операции пересылки.
Выкладываю свой код, буду очень благодарна если кто-нибудь подскажет где ошибка:
Не могу разобраться, очень прошу помочь. Заранее Благодарю!
Решение задачи: «Сортировка выбором подсчет обменов»
textual
Листинг программы
Program Selekt;
uses crt;
const m=100;
var a:array[1..m] of Integer;
i,j,n,srav,obmn,min,k,t:Integer;
begin
writeln('SELEKTSORT');
write('Vvedite n=');
readln(n);
writeln('MASS TO');
randomize;
for i:=1 to n do
begin
a[i]:=Random(100);
Write(a[i]:4);
end;
writeln;
srav:=0; //сравнения
obmn:=0; //обмены
for i:=1 to n-1 do
begin
min:=i;
k:=0;
for j:=i+1 to n do
begin
inc(srav);
if a[j]<a[min] then
begin
min:=j;
k:=1;
end;
end;
if k=1 then
begin
t:=a[i];
a[i]:=a[min];
a[min]:=t;
inc(obmn)
end;
end;
writeln('MASS AFTER');
for i:=1 to n do
write(a[i]:4);
writeln;
writeln('Kol-vo obmenov=',obmn);
writeln('Kol-vo sravnenij=',srav);
end.
Объяснение кода листинга программы
- Создание программы с названием
Selektи использованием библиотеки CRT. - Объявление константы m=100 и переменной a типа массив целых чисел с размером m.
- Объявление восьми переменных: i, j, n, srav, obmn, min, k, t типа Integer.
- Вывод на экран сообщения
SELEKTSORT. - Сбор данных от пользователя: ввод значения переменной n.
- Инициализация массива a случайными значениями от 0 до 99.
- Вывод на экран заполненного массива a.
- Инициализация переменных srav и obmn со значениями 0. Переменная srav отвечает за количество сравнений, а obmn за количество обменов.
- Проверка каждого элемента массива a на предмет того, является ли он минимальным.
- Если текущий элемент меньше минимального, то он становится новым минимальным, а переменная k принимает значение 1.
- Если переменная k равна 1, то происходит обмен текущего элемента с минимальным. Переменная obmn увеличивается на 1.
- Вывод на экран отсортированного массива a.
- Вывод на экран количества обменов (obmn) и количества сравнений (srav).
- Конец программы.