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

Материал из Algocode wiki
Версия от 22:59, 14 августа 2019; Grphil (обсуждение | вклад) (Новая страница: «==Алгоритм== Одним из самых понятных и придумываемых способов отсортировать массив явля...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Алгоритм

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

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

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

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

Так как мы $N$ раз искали максимум среди примерно $N$ чисел, то асимптотика составляет $O(N^2)$



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

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