0

Вот участок кода с сортировкой:

//Сортировка вставками
  for ($i = 1; $i < count($arr2); $i++) {
    $x = $arr2[$i];
    for ($j = $i - 1; $j >= 0 && $arr2[$j] > $x; $j--) {
      /* сдвигаем элементы вправо, пока выполняется условие
         $a[$j] > $a[$i] */
      $arr2[$j + 1] = $arr2[$j];
    }
    // на оставшееся после сдвига место, ставим $a[$i]
    $arr2[$j + 1] = $x;
  }

Что и куда нужно добавить, что бы посчитать количество сравнений и перестановок?

8
  • ну как минимум переменые нормально обозвать
    – Naumov
    5 апр 2017 в 14:54
  • @Naumov а дальше?
    – Alexander
    5 апр 2017 в 14:56
  • ввести переменную которая будет содержать подщитаную сумму. О каких сравнениях речь?
    – Naumov
    5 апр 2017 в 15:02
  • Это алгоритм сортировки вставками, он сравнивает элементы (целые числа), и сдвигает их, если они расположены не по возрастанию. Вот количество этих сравнений и сдвигов надо посчитать.
    – Alexander
    5 апр 2017 в 15:07
  • вы попробуйте вообще разобраться как работает алгоритм, тогда может и ответ станет очевидным?
    – teran
    5 апр 2017 в 15:13

1 ответ 1

0

Классический алгоритм сортировки вставками предполагает три основные операции на каждый элемент:

  1. Двоичный поиск места вставки.
  2. Перестановку группы элементов на соседние места.
  3. Вставку нового элемента на своё место.

Операции по п.1 - это "чистые" сравнения. Операции п.2 - это сдвиг области памяти, который допускает разные варианты реализации в зависимости от формата исходных данных (для битовых полей - одни, для 1-байтовых данных - другие, для объектов сравниваемые и перемещаемые данные вообще лежат в разных местах...).

В рассматриваемой программе форматы сравниваемых и исходных данных совпадают, что позволяет при отказе от бинарного поиска совместить сравнения и перестановки. Т.е.

  1. Счётчик перестановок следует инкрементировать во внутреннем цикле.
  2. Счётчик сравнений - во внешнем цикле.
  3. По окончании циклов к показаниям счётчика сравнений следует добавлять показания счётчика перестановок, после чего умножить их на 2 (если есть сравнение j >= 0) или 1 (если его нет).
  4. Следует указать, что формат исходных данных изначально требует по n дополнительных сравнений для n-1 переставляемого элемента, за счёт чего бинарный поиск добавляет по две или по одной операции на элемент соответственно.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.