Сортировка выбором: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Алгоритм== Одним из самых понятных и придумываемых способов отсортировать массив явля...»)
 
 
Строка 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$ чисел, то асимптотика составляет $O(N^2)$
+
Наш алгоритм каждый раз ищет максимальное число из оставшихся, всего чисел в массиве - $n$, следовательно искать максимум мы будем $n$ раз, также каждый раз у нас останется не более $n$ чисел, тогде асимптотика составляет $O(N \cdot N) = O(N^2)$
  
 
{{Автор|Полина Романченко|Romanchenko}}
 
{{Автор|Полина Романченко|Romanchenko}}
 +
{{Автор|Глеб Лобанов|glebodin}}
 
[[Категория:Квадратичные сортировки]]
 
[[Категория:Квадратичные сортировки]]
 
[[Категория:Конспект]]
 
[[Категория:Конспект]]

Текущая версия на 11: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