Selection Sort
Selection Sort — алгоритм, который находит минимум в неотсортированной части и ставит его в начало.
Основная идея
Для каждой позиции выбирается минимальный элемент и меняется местами с текущим.
Пошаговый пример
Исходный массив:
[6, 2, 9, 1, 4]- Минимум в массиве — 1, меняем с первым элементом → [1, 2, 9, 6, 4]
- Следующий минимум в хвосте — 2, уже на месте
- Дальше ставим 4 и 6 на свои позиции → [1, 2, 4, 6, 9]
Псевдокод
for i from 0 to n - 2:
min_index = i
for j from i + 1 to n - 1:
if arr[j] < arr[min_index]:
min_index = j
swap(arr[i], arr[min_index])
Оптимизация: Минимум записей в память: обычно один swap на проход.
Сложность
Время
O(n²) во всех случаях.
Память
O(1), in-place.
Когда используется
- Когда важны минимальные записи
- Обучение
- Малые наборы данных
Ключевые свойства
- Не стабильный
- In-place
- Предсказуемая сложность