Сортировка выбором подсчет обменов - 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).
- Конец программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д