Сортировка выбором: различия между версиями
Grphil (обсуждение | вклад) (Новая страница: «==Алгоритм== Одним из самых понятных и придумываемых способов отсортировать массив явля...») |
Глеб (обсуждение | вклад) |
||
Строка 4: | Строка 4: | ||
Чтобы отсортировать массив, нужно просто $N$ раз выбрать минимум среди еще неотсортированных чисел. То есть на $i$-ом шаге ищется минимум на отрезке $[i, n - 1]$, и этот минимум меняется с $i$-ым элементом, теперь отрезок $[0, i]$ отсортирован. | Чтобы отсортировать массив, нужно просто $N$ раз выбрать минимум среди еще неотсортированных чисел. То есть на $i$-ом шаге ищется минимум на отрезке $[i, n - 1]$, и этот минимум меняется с $i$-ым элементом, теперь отрезок $[0, i]$ отсортирован. | ||
+ | ==Реализация== | ||
+ | |||
+ | <syntaxhighlight lang="C++" line='line'> | ||
+ | for (i = 0; i < n - 1; i++) { | ||
+ | for (j = i + 1; j < n; j++) { | ||
+ | if (a[i] > a[j]) { | ||
+ | swap(a[j], a[i]); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
[https://visualgo.net/nl/sorting Красивая визуализация] (вкладка SEL) | [https://visualgo.net/nl/sorting Красивая визуализация] (вкладка SEL) | ||
==Оценка времени работы== | ==Оценка времени работы== | ||
− | + | Наш алгоритм каждый раз ищет максимальное число из оставшихся, всего чисел в массиве - $n$, следовательно искать максимум мы будем $n$ раз, также каждый раз у нас останется не более $n$ чисел, тогде асимптотика составляет $O(N \cdot N) = O(N^2)$ | |
{{Автор|Полина Романченко|Romanchenko}} | {{Автор|Полина Романченко|Romanchenko}} | ||
+ | {{Автор|Глеб Лобанов|glebodin}} | ||
[[Категория:Квадратичные сортировки]] | [[Категория:Квадратичные сортировки]] | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Текущая версия на 08:47, 13 сентября 2019
Алгоритм
Одним из самых понятных и придумываемых способов отсортировать массив является сортировка выбором минимума (или максимума).
Чтобы отсортировать массив, нужно просто $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