V
V
Ventus2020-03-16 15:54:09
Algorithms
Ventus, 2020-03-16 15:54:09

Is the number of moves counted correctly in insertion sort?

Insertion sorting of an array is implemented in 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);
};

If elements are being moved, then the counter is incremented by 3 because there are 3 operations on the elements.

For an array with a thousand elements, the following average results are obtained:

Number of comparisons: 4950 (always the same)
Number of moves: 7896 (floats around 6000-8000).

Question: am I counting the number of movements correctly?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
0
0xD34F, 2020-03-16
@Ventus

If elements are moved, the counter is incremented by 3 because there are 3 element operations.

And if the exchange were implemented like this: Or even like this:
[ arr[j - 1], arr[j] ] = [ arr[j], arr[j - 1] ];
swap(arr, j - 1, j); // функция меняет местами элементы, но как именно - вам неизвестно

By how much would you increment the counter? Don't need 3, write 1. Treat the exchange as a single operation.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question