Сортировка простым выбором - посчитать число обменов - 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;

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

В этом коде выполняется сортировка массива методом простого выбора. Суть этого метода заключается в том, что на каждом шаге выбирается минимальный элемент из неотсортированной части массива и меняется на первое место неотсортированной части. Затем этот процесс повторяется для следующей неотсортированной части массива до тех пор, пока массив не будет полностью отсортирован. Вот список действий, выполняемых в коде:

  1. Инициализация переменной k, которая будет отслеживать количество обменов.
  2. Проход по массиву от 1 до n-1.
  3. На каждом шаге ищется минимальный элемент в неотсортированной части массива (от текущего до конца массива).
  4. Если найденный минимальный элемент больше текущего индекса, то происходит обмен этого элемента с текущим элементом.
  5. Увеличивается значение переменной k на 1.
  6. После завершения цикла переменная k будет содержать количество обменов.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.857 из 5
Похожие ответы