Сортировка выбором

Алгоритм

Одним из самых понятных и придумываемых способов отсортировать массив является сортировка выбором минимума (или максимума).

Чтобы отсортировать массив, нужно просто $N$ раз выбрать минимум среди еще неотсортированных чисел. То есть на $i$-ом шаге ищется минимум на отрезке $[i, n - 1]$, и этот минимум меняется с $i$-ым элементом, теперь отрезок $[0, i]$ отсортирован.

Реализация

1 for (i = 0; i < n - 1; i++) {
2     for (j = i + 1; j < n; j++) {
3         if (a[i] > a[j]) {
4             swap(a[j], a[i]);
5         }
6     }
7 }

Красивая визуализация (вкладка SEL)

Оценка времени работы

Наш алгоритм каждый раз ищет максимальное число из оставшихся, всего чисел в массиве - $n$, следовательно искать максимум мы будем $n$ раз, также каждый раз у нас останется не более $n$ чисел, тогде асимптотика составляет $O(N \cdot N) = O(N^2)$

---

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin