Записки погромиста

Простое объяснение.

Что такое Selection Sort?

Selection Sort (сортировка выбором) — это алгоритм, который находит самое маленькое число в списке, ставит его на первое место, затем находит следующее по величине и ставит его на второе место, и так далее, пока весь список не будет отсортирован.

Как работает Selection Sort?

Давайте посмотрим, как работает алгоритм на примере. У нас есть список чисел, который нужно отсортировать по возрастанию:

[5, 3, 8, 4, 2]

Наша цель — отсортировать этот список, чтобы он выглядел так: [2, 3, 4, 5, 8].

Шаги алгоритма Selection Sort

1. Найди самое маленькое число в списке.
2. Поменяй его местами с первым числом.
3. Перейди ко второму числу и найди самое маленькое среди оставшихся чисел.
4. Поменяй его местами со вторым числом.
5. Продолжай повторять этот процесс, пока не отсортируешь весь список.

Пошаговый пример

Давайте разберем это на примере [5, 3, 8, 4, 2].

Первый проход (ищем самое маленькое число)

1. Смотрим на весь список: [5, 3, 8, 4, 2].
2. Самое маленькое число здесь — 2.
3. Меняем местами 2 и первое число (5).
4. Теперь список выглядит так: [2, 3, 8, 4, 5].

Второй проход (ищем следующее по величине число)

1. Теперь смотрим на оставшийся список (начиная со второго числа): [3, 8, 4, 5].
2. Самое маленькое число здесь — 3 (он уже стоит на втором месте).
3. Так как 3 уже на своем месте, ничего не меняем.
4. Список остаётся [2, 3, 8, 4, 5].

Третий проход (ищем следующее по величине число)

1. Смотрим на оставшиеся числа: [8, 4, 5].
2. Самое маленькое здесь — 4.
3. Меняем местами 8 и 4.
4. Список теперь выглядит так: [2, 3, 4, 8, 5].

Четвертый проход (ищем следующее по величине число)

1. Остаются только два числа: [8, 5].
2. Самое маленькое — 5.
3. Меняем местами 8 и 5.
4. Теперь наш список отсортирован: [2, 3, 4, 5, 8].

Готово! Мы прошли по списку и расставили все числа по порядку.

Реализация Selection Sort в JavaScript

Теперь, когда мы поняли принцип работы, давайте посмотрим, как этот алгоритм выглядит в коде на JavaScript:

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[i]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]; // Меняем местами, если нашли меньшее значение
      }
    }
  }
  return arr;
}

// Пример использования
let numbers = [5, 3, 8, 4, 2];
console.log(selectionSort(numbers)); // Вывод: [2, 3, 4, 5, 8]

Как работает этот код?

1. Внешний цикл for (let i = 0; i < arr.length; i++): проходит по каждому элементу массива.
2. Внутренний цикл for (let j = i + 1; j < arr.length; j++): ищет элемент меньше текущего.
3. Если находим меньший элемент (arr[j] < arr[i]), меняем его местами с текущим элементом с помощью [arr[i], arr[j]] = [arr[j], arr[i]].

Таким образом, минимальное значение для каждой позиции «всплывает» в начало списка.