Правильно ли подсчитано количество перемещений в сортировке вставками?

Question

[Ventus]

На JavaScript реализована сортировка массива вставками:

const sort = (arr) => {
  let compCounter = 0; // счетчик сравнений
  let movementCounter = 0; // счетчик перемещений элементов
  const arrLength = arr.length;
  
	for (let i = 1; i < arrLength; i++) {
		for (let j = i; j > 0; j--) {
      if (arr[j - 1] > arr[j]) { 
        const temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
        movementCounter += 3;
      }

      compCounter += 1;
		}    
	}
  
  console.log('Количество сравнений: ', compCounter);
  console.log('Количество перемещений: ', movementCounter);
};

Если происходит перемещение элементов, то счетчик увеличивается на 3, потому что происходит 3 операции с элементами.

Для массива с тысячью элементов, получаются следующие усреденные результаты:

Количество сравнений: 4950 (всегда одинаково)
Количество перемещений: 7896 (плавает в районе 6000-8000).

Вопрос: правильно ли я считаю количество перемещений?

Answer 1

[0xD34F]

Если происходит перемещение элементов, то счетчик увеличивается на 3, потому что происходит 3 операции с элементами.

А если бы обмен был реализован так:

[ arr[j - 1], arr[j] ] = [ arr[j], arr[j - 1] ];

Или даже так:

swap(arr, j - 1, j); // функция меняет местами элементы, но как именно - вам неизвестно

На сколько бы вы увеличивали счётчик? Не надо 3, пишите 1. Рассматривайте обмен как единую операцию.

Comments

[Ventus]

Спасибо!

Answer 2

[german11235]

Если вы знакомы с термином асимптотическая сложность и понимаете как она высчитывается, то осознаёте, что зависимость O(const * n^2) останется прежней. Считая каждую инструкцию по отдельности вы просто манипулируете константой стоящей спереди.

Для наглядности отношения количества сравнений к количеству обменов я бы порекомендовал

const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;

выделить в одну операцию.

Также у Вас неверно реализована сама сортировка, о чём и говорит статичное количество сравнений.

Comments

[Ventus]

Спасибо!

А по поводу сортировки: получается, накосячил. В рамках написания программы я изменил код, потому что иначе в циклах, которые не проходят условия, невозможно увеличить счетчик сравнений.

Вот другой "стандартный" вариант для JS:

const insertionSort = (a) => {
  const arrLength = a.length; // количество элементов в массиве
  let compCounter = 0; // счетчик сравнений
  let movementCounter = 0; // счетчик перемещений элементов

  for (let i = 0; i < arrLength; i += 1) { // Выполняется для каждого элемента массива.
    let v = a[i], j = i - 1; // Определяется значение текущего элемента, а также индекс предыдущего элемента.
    while(j >= 0 && a[j] > v) { // Пока индекс предыдущего элемента >= 0 и его значение больше значения текущего элемента.
      a[j + 1] = a[j]; // Значением следующего за текущим элемента массива становится значение предыдущего элемента.
      j -= 1;
      movementCounter += 1;	
    }
    a[j + 1] = v; // Значением следующего за текущим элемента массива становится значение текущего элемента
  }

  console.log('Количество сравнений: ', compCounter);
  console.log('Количество перемещений: ', movementCounter);
};

Голову сломал над тем, куда можно поместить compCounter, чтобы он учитывал сравнения в каждом цикле (даже тех, что не прошли условия).

[german11235]

Ventus, почему не поместить movementCounter += 1 перед while и внутри?

[Ventus]

CosmoV, movementCounter работает корректно. Вы, наверно, имели в виду compCounter (количество сравнений)?

Если поместить его перед while, то данные будут некорректными - количество сравнений всегда будет равно количеству элементов в массиве.

А как реализовать счетчик сравнений в условиях цикла (внутри круглых скобок) в рамках языка JS, я не знаю. Такого еще не встречал.

Или вы имели в виду вообще в самом цикле? После фигурных скобок? Тогда это тоже не имеет смысла - данные будут некорректными.

[german11235]

Ventus, да, я имел в виду compCounter. Попробуйте поменять входные данные, чтобы увидеть изменение количества сравнений. Также посмотрите внимательнее на стоимость операций сортировки по ссылке, что приводил выше. Конкретнее на C4 и C5, количество сравнений на одно больше количества обменов на каждой итерации цикла.

[german11235]

Ventus, я имел в виду

compCounter += 1;
    while(j >= 0 && a[j] > v) {
      a[j + 1] = a[j];
      j -= 1;
      movementCounter += 1;
      compCounter += 1	
    }

[Ventus]

CosmoV, да, именно так я сейчас и сделал. Посмотрел на С4 и С5. Получается, количество сравнений всегда будет больше количества перемещений ровно на количество элементов массива?

Вот реализовал на repl для массива размером в 100 элементов: https://repl.it/repls/ConventionalSilkyOperation