Визуализация
Данные: Случайные
Легенда цветов
Как работает сортировка выбором
Суть метода: Мы делим массив на две части: левую (отсортированную) и правую (неотсортированную). Алгоритм находит самый маленький элемент в правой части и меняет его местами с первым элементом правой части. Таким образом, отсортированная часть увеличивается на один элемент.
Пошаговый процесс:
- Принимаем первый неотсортированный элемент за текущий минимум.
- Проходим по остатку массива и сравниваем каждый элемент с текущим минимумом.
- Если находим элемент меньше, он становится новым текущим минимумом.
- Дойдя до конца, меняем местами найденный минимум с первым неотсортированным элементом.
В отличие от сортировки пузырьком, здесь происходит минимум обменов (не более O(n) раз за весь алгоритм), так как мы обмениваем элементы только один раз за проход.
Синонимы названия: Линейный выбор с обменом, Selection Sort.
Сложность алгоритма
Сортировка выбором всегда работает одинаково долго. Ей абсолютно неважно, отсортирован массив заранее или нет - она в любом случае будет просматривать всю оставшуюся часть в поисках минимума.
По времени
| Случай | Время | Комментарий |
|---|---|---|
| Лучший случай | O(n²) | Даже если массив уже отсортирован, алгоритм вынужден проверять все элементы. |
| Средний случай | O(n²) | В среднем потребуется n(n-1)/2 сравнений. |
| Худший случай | O(n²) | Алгоритм всегда делает одинаковое количество сравнений. |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(1) | Сортировка происходит "на месте" (in-place). |
Устойчивость алгоритма
Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Устойчивость | Нет | Из-за обменов на большие расстояния алгоритм может нарушить порядок одинаковых элементов (например, если минимум обменивается с первым из группы равных). |
Примеры реализации сортировки выбором (Selection Sort)
Код на C
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Считаем, что минимум на позиции i
int min_idx = i;
// Ищем настоящий минимум в оставшейся части
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Если нашли элемент меньше, обмениваем их
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}Код на Python
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
# Индекс текущего минимума
min_idx = i
# Сканируем оставшуюся часть массива
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Меняем местами, если нашли элемент меньше
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]Код на JavaScript
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j; // Нашли новый минимум
}
}
if (minIdx !== i) {
let temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
return arr;
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про сортировку выбором - с подробной теорией, задачами и проверочными вопросами.