Учебник по информатике и математике
Темы
C++
Основы языка
Сортировка выбором
Оглавление:
Ты расставляешь учебники на полке по высоте. Скорее всего, ты сделаешь так: найдешь самый низкий и поставишь его первым. Потом среди оставшихся снова найдешь самый низкий и поставишь вторым. И так, пока книги не кончатся.
Это и есть сортировка выбором: на каждом шаге выбираем наименьший элемент из еще не расставленных и ставим его на следующее место. Алгоритм простой, и в нем нет ничего нового, если ты умеешь искать минимум в массиве.
Идея алгоритма
Массив делится на две части: слева — уже отсортированная, справа — еще нет. В начале отсортированная часть пустая. На шаге с номером $i$ (считая с нуля):
- Ищем минимум в неотсортированной части — от
a[i]до конца массива. Это обычный поиск минимума за один проход. - Меняем найденный минимум местами с
a[i]. - Отсортированная часть выросла на один элемент.
После $n - 1$ шагов последний элемент сам оказывается на месте: он больше всех остальных.
Ключевая идея: Запоминаем не значение минимума, а его индекс. Без индекса не получится поменять минимум местами с
a[i].
Разбор на примере
Высота книг в сантиметрах: [26, 21, 30, 17, 23].
| Шаг | Где ищем минимум | Минимум | Обмен | Массив после шага |
|---|---|---|---|---|
| 1 | [26, 21, 30, 17, 23] |
17 | 26 и 17 | [17, 21, 30, 26, 23] |
| 2 | [21, 30, 26, 23] |
21 | не нужен | [17, 21, 30, 26, 23] |
| 3 | [30, 26, 23] |
23 | 30 и 23 | [17, 21, 23, 26, 30] |
| 4 | [26, 30] |
26 | не нужен | [17, 21, 23, 26, 30] |
Обрати внимание: после третьего шага массив уже отсортирован, но алгоритм об этом не знает и все равно ищет минимум на четвертом шаге. В отличие от пузырька, сортировка выбором не умеет заканчивать раньше.
Реализация
Переменная m хранит индекс минимума. На втором и четвертом шаге примера минимум уже стоит на месте, и код меняет элемент сам с собой — ничего не портится, поэтому отдельную проверку не пишем.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
m = i # индекс минимума в неотсортированной части
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i] # ставим минимум на место i
books = [26, 21, 30, 17, 23]
selection_sort(books)
print(books) # [17, 21, 23, 26, 30]
То же на C++:
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
void selectionSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[m]) m = j;
swap(a[i], a[m]);
}
}
int main() {
vector<int> books = {26, 21, 30, 17, 23};
selectionSort(books);
for (int x : books) cout << x << " "; // 17 21 23 26 30
cout << "\n";
}
Сложность
На первом шаге поиск минимума делает $n - 1$ сравнение, на втором $n - 2$, и так до одного:
Число сравнений не зависит от того, каким был массив, поэтому сложность всегда $O(n^2)$ — даже если массив уже отсортирован. Зато обменов не больше $n - 1$, по одному на шаг. Дополнительная память — $O(1)$.
Сравним с сортировкой пузырьком:
| Что сравниваем | Пузырьком | Выбором |
|---|---|---|
| Сравнений | до $\frac{n(n - 1)}{2}$ | всегда $\frac{n(n - 1)}{2}$ |
| Обменов | до $\frac{n(n - 1)}{2}$ | не больше $n - 1$ |
| Уже отсортированный массив | $O(n)$ с ранним выходом | $O(n^2)$ |
| Порядок равных элементов | сохраняется | может нарушиться |
Последняя строка важна, когда сортируют не числа, а записи. Пусть оценки с именами: [5 Аня, 5 Боря, 3 Вика]. Первый шаг найдет тройку и поменяет местами Аню и Вику: [3 Вика, 5 Боря, 5 Аня]. Теперь Аня стоит после Бори, хотя в начале было наоборот. Пузырек меняет только соседей, которые стоят неправильно, поэтому равные элементы у него никогда не меняются местами.
Мало обменов — главное достоинство сортировки выбором. Оно пригодится, когда сравнить дешево, а переставить дорого: например, на складе посмотреть на этикетку ящика легко, а передвинуть сам ящик — долго.
Частая ошибка: Внутренний цикл с 0 вместо
i + 1. Тогда минимум каждый раз находится в уже отсортированной части, и алгоритм ломает собственную работу: из[26, 21, 30, 17, 23]получится[21, 30, 26, 17, 23]. Другая ловушка — менять элементы местами сразу, как только нашелся меньший. Массив отсортируется, но обменов станет гораздо больше, и пропадет главное преимущество алгоритма.
Проверь себя
Сколько сравнений сделает сортировка выбором, если массив из 5 элементов уже отсортирован?
Массив [6, 3, 8, 1] сортируют выбором. Какое число будет стоять на последнем месте (индекс 3) после первого шага?
Соедини характеристику сортировки выбором и ее значение.
Сравнений при $n = 5$
10
Наибольшее число обменов при $n = 5$
$O(1)$
Сложность на уже отсортированном массиве
4
Дополнительная память
$O(n^2)$