Сортировка выбором
Материал из Algocode wiki
Версия от 19:59, 14 августа 2019; Grphil (обсуждение | вклад) (Новая страница: «==Алгоритм== Одним из самых понятных и придумываемых способов отсортировать массив явля...»)
Алгоритм
Одним из самых понятных и придумываемых способов отсортировать массив является сортировка выбором минимума (или максимума).
Чтобы отсортировать массив, нужно просто $N$ раз выбрать минимум среди еще неотсортированных чисел. То есть на $i$-ом шаге ищется минимум на отрезке $[i, n - 1]$, и этот минимум меняется с $i$-ым элементом, теперь отрезок $[0, i]$ отсортирован.
Красивая визуализация (вкладка SEL)
Оценка времени работы
Так как мы $N$ раз искали максимум среди примерно $N$ чисел, то асимптотика составляет $O(N^2)$
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko