Предположим, мы хотим отсортировать список по убыванию. Одна из самых простых, но не самых эффективных сортировок — сортировка выбором.
Как работает сортировка выбором: мы проходимся с самого начала по всему списку и находим максимальное число. Ставим его на первое место. Теперь проходимся по всему списку ещё раз, но уже начиная со второго элемента (на первом месте уже и так самое большое число). Находим максимум и ставим на второе место. Проходимся еще раз, начиная с третьего элемента и ищем максимум. И так пока не закончим.
Какая сложность у сортировки выбором? При первом проходе будет O(n), потому что проверяем каждый элемент. При втором проходе будет O(n-1), потому что первый уже проверен. Далее будет O(n-2), O(n-3) и т.д. В среднем получится 1/2*n. И учитываем, что вот эти проходы будут внутри цикла, который проверяет каждый элемент — O(n). Итого: O(n * 1/2 * n) = O(1/2 * n^2). Но есть такое негласное правило, что константы просто отбрасываем, поэтому сложность получается O(n^2).
В книге был пример, где создавался ещё один список, но я не стала так делать, чтобы не занимать лишнюю память.
Создала отдельный проект для алгоритмов. Так удобней, чтобы можно было сразу запустить и потыкать везде: https://github.com/Ladgertha/Algorithms
