Временная сложность
Лучший: O(n²)
Средний: O(n²)
Худший: O(n²)
Selection Sort разделяет массив на отсортированную и неотсортированную области. Алгоритм многократно выбирает наименьший элемент из неотсортированной области и перемещает его в конец отсортированной области.
Как работает алгоритм:
1. Найти минимальный элемент в неотсортированной части
2. Поменять его местами с первым неотсортированным элементом
3. Сдвинуть границу между отсортированной и неотсортированной областями на одну позицию вправо
4. Повторять, пока весь массив не будет отсортирован
Временная сложность:
Лучший случай: O(n²)
Средний случай: O(n²)
Худший случай: O(n²)
Пространственная сложность: O(1) — сортировка на месте
Свойства:
- Нестабильный алгоритм (может изменять относительный порядок равных элементов)
- Неадаптивный
- Сортировка на месте
- Минимизирует количество обменов: O(n)
Полезен в случаях, когда операции записи в память обходятся дорого, поскольку выполняет не более O(n) обменов.
Похожие алгоритмы
Частые вопросы
- Что такое Сортировка выбором (Selection Sort)?
- Selection Sort разделяет массив на отсортированную и неотсортированную области. Алгоритм многократно выбирает наименьший элемент из неотсортированной области и перемещает его в конец отсортированной области.
- Какова сложность Сортировка выбором (Selection Sort)?
- Время (среднее): O(n²) · Память: O(1)
- Для кого предназначена визуализация Сортировка выбором (Selection Sort)?
- Визуализация Сортировка выбором (Selection Sort) рассчитана на начальный уровень в категории «Сортировка». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Сортировка выбором (Selection Sort)?
- В той же категории (Сортировка) вы можете изучить: Bubble Sort, Insertion Sort, Quick Sort. Каждый из них имеет интерактивную визуализацию.