@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).

Вопрос: правильно ли я считаю количество перемещений?
  • Вопрос задан
  • 101 просмотр
Решения вопроса 2
0xD34F
@0xD34F
Если происходит перемещение элементов, то счетчик увеличивается на 3, потому что происходит 3 операции с элементами.

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

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

Или даже так:

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

На сколько бы вы увеличивали счётчик? Не надо 3, пишите 1. Рассматривайте обмен как единую операцию.
Ответ написан
@CosmoV
Если вы знакомы с термином асимптотическая сложность и понимаете как она высчитывается, то осознаёте, что зависимость O(const * n^2) останется прежней. Считая каждую инструкцию по отдельности вы просто манипулируете константой стоящей спереди.

Для наглядности отношения количества сравнений к количеству обменов я бы порекомендовал
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
выделить в одну операцию.

Также у Вас неверно реализована сама сортировка, о чём и говорит статичное количество сравнений.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы