Почему алгоритм сортировки выбором выполняет столько же операций для поиска индекса в массиве, сколько и пузырьковый? Как это возможно?

Рейтинг: 0Ответов: 1Опубликовано: 12.07.2023

Имеется два алгоритма, почему кол-во операций в переменных счетчиках count и count2 одинаковое, если алгоритмы разные?

И вообще правильно ли я написал алгоритм сортировки пузырьком?

const arr = [
  0, 3, 2, 5, 6, 8, 1, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6, 3,
  32,
]

let count = 0
let count2 = 0

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[i]) {
        let temp = array[j]
        array[j] = array[i]
        array[i] = temp
      }
      count += 1
    }
  }
  return array
}

// console.log('length', arr.length)
console.log(bubbleSort(arr)) // O(n*n)
console.log('bubble count = ', count)

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let indexMin = i
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[indexMin]) {
        indexMin = j
      }
      count2 += 1
    }
    let temp = array[i]
    array[i] = array[indexMin]
    array[indexMin] = temp
  }
  return array
}

console.log(selectionSort(arr))
// console.log(arr.length) // O(n*n)
console.log(' count = ', count2)

Ответы

▲ 3Принят

Уберём из bubblesort всё что не относится к счётчику:

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      count += 1
    }
  }
}

Уберём из selectionSort всё что не относится к счётчику:

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      count2 += 1
    }
  }
}

Удивление ещё не прошло? Вы считаете двумя способами одно и то же число. Называется оно треугольным.

2.

Нет, это не пузырёк. В любом пузырьке местами меняются только соседние элементы. В вашем коде вы меняете далёкие друг от друга элементы.