3_selection-sort.js

// Сортировка выбором(Selection Sort)

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;

// Суть: Есть массив неупорядоченных элементов. Находим в цикле МИНИМАЛЬНЫЙ элемент,
// затем меняем местами с первым элементом, затем опять пробегаемся по массиву и находим минимальное значение,
// но меняем его уже со вторым элементом, затем с 3,4 итд пока не будет отсортирован весь массив.
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;
      }
      count += 1;
    }

    // Меняем местами минимальный элемент с current элементом (i)
    let tmp = array[i];
    array[i] = array[indexMin];
    array[indexMin] = tmp;
  }

  // Возвращаем отсортированный массив
  return array;
}

// Кол-во итераций 325. Длина массива 26. Таким образом O(1/2*n*n),
// но коэффициенты в оценке сложности алгоритма не учавствуют. Поэтому будет O(n*n)
console.log(selectionSort(arr));
console.log(arr.length);
console.log("count = ", count);