Сортировка простым выбором - посчитать число обменов - Turbo Pascal
Формулировка задачи:
Здравствуйте.
Не могу понять как посчитать количество обменов при сортировке простым выбором
Я думала обмен - это когда меняется местами очередной мин элемент и текущий (i-тый из внешнего цикла).
Получилась такая программа:
Но потом в методичке нашла формулы для сравнения:
Среднее число обменов - n*(ln(n)+0.577216) (это для массива из 10 чисел - 28)
Лучший вариант (когда массив отсортирован) 3*(n-1)); (это для массива из 10 чисел - 27)
Худший sqr(n)/4+3*(n-1)); (это для массива из 10 чисел - 52)
Т.е. у меня совсем не то, что надо
А надо: необходимо ввести в программу целочисленный счетчик (устанавливаемый в 0 в начале работы алгоритма сортировки), который будет увеличиваться на единицу после каждой операции обмена (т.е. операции присваивания, в правой или левой части которой встречается элемент массива a).
Я не совсем понимаю что считать то?
Вот так? Счетчик добавлен в 5, 10, 14 и 16 строки или из 16 строки убрать?
Помогите пожалуйста!
Решение задачи: «Сортировка простым выбором - посчитать число обменов»
textual
Листинг программы
k := 0; for i := 1 to n - 1 do begin imin := i; for j := i + 1 to n do if a[j] < a[imin] then imin := j; //это не обмен, это поиск подходящего элемента if imin > i //если подходящий элемент найден, then begin //то обмениваем элементы inc(k); //считаем количество обменов x := a[i] //и обмениваем a[i] := a[imin]; a[imin] := x end end;
Объяснение кода листинга программы
В этом коде выполняется сортировка массива методом простого выбора. Суть этого метода заключается в том, что на каждом шаге выбирается минимальный элемент из неотсортированной части массива и меняется на первое место неотсортированной части. Затем этот процесс повторяется для следующей неотсортированной части массива до тех пор, пока массив не будет полностью отсортирован. Вот список действий, выполняемых в коде:
- Инициализация переменной k, которая будет отслеживать количество обменов.
- Проход по массиву от 1 до n-1.
- На каждом шаге ищется минимальный элемент в неотсортированной части массива (от текущего до конца массива).
- Если найденный минимальный элемент больше текущего индекса, то происходит обмен этого элемента с текущим элементом.
- Увеличивается значение переменной k на 1.
- После завершения цикла переменная k будет содержать количество обменов.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д