Сортировка выбором
На каждом шаге ищет минимальный элемент в неотсортированной части и ставит его на своё место.
Идея алгоритма
Массив условно делится на отсортированную и неотсортированную части. Сначала отсортированная часть пуста. На каждом шаге мы ищем минимум в неотсортированной части и меняем его местами с первым элементом этой части. Отсортированная область растёт слева направо.
Асимптотика:
- Время (любой случай): O(n²)
- Память: O(1)
- Не является стабильной сортировкой
Когда использовать
- Когда важна простота реализации
- Когда стоимость обмена элементов низкая
- Для очень маленьких массивов и учебных примеров
Плюсы
- Простая идея и реализация;
- Минимальное число обменов элементов;
- Предсказуемое поведение независимо от входных данных.
Минусы
- Такая же квадратичная сложность, как у пузырьковой сортировки;
- Работает медленно на больших массивах;
- Не стабильный алгоритм — порядок равных элементов может меняться.
Пример кода
function selectionSort(arr) {
const a = [...arr];
const n = a.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[a[i], a[minIndex]] = [a[minIndex], a[i]];
}
}
return a;
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания