Квадратичные сортировки. Сортировка выбором.

В Трешландии строго следят за порядком. За каждым жителем фиксируют нарушения, и к злостным нарушителям применяют штрафные санкции. Хулиганов могут лишить права подольше спать в выходные, есть мороженое, петь в душе. А могут и отправить на исправительные работы: например, собирать червяков на улице после дождя, дрессировать белок в парке, отгонять жуков от кабачков. Особо провинившимся дают задание — научить немого попугая короля Кондратия петь песни Rammstein.

Есть специальный журнал, в котором отмечается количество нарушений за неделю для каждого жителя.

В конце каждой недели определяют самых злостных нарушителей. Для этого нужно отсортировать список по убыванию.

Как это сделать?

Например, выбрать из списка наибольший элемент. Пройдя по массиву, можно определить, что Феликс вёл себя хуже всех, у него аж 30 нарушений. Кажется, ему пора начинать учить немецкий.

Феликса нужно добавить в новый массив и удалить из исходного.

Далее нужно выбрать элемент с наибольшим значением из оставшихся. И на втором месте — Алиса Ермолаева, у неё 11 нарушений. Алису нужно добавить в новый массив и удалить из исходного.

Аналогично нужно поступить с Гришей Бенидиктовым.

Делаем так до тех пор, пока не закончится исходный список. В итоге получим список, отсортированный по убыванию, который начинается с жителя с наибольшим числом нарушений и оканчивается наименьшим.

Задача решена, осталось назначить наказания!

На каждом шаге алгоритма выбирали элемент с наибольшим значением из оставшихся.

Какая у него вычислительная сложность?

Всего шагов $n$, где $n$ — количество жителей.

Что происходит на каждом шаге?

Мы проходим по всему массиву и выбираем элемент с максимальным значением. Сложность этой операции $O(n)$. Найденный элемент добавляем в новый массив. Стоимость такой операции $O(1)$. Затем удаляем этот элемент из старого массива.

Таким образом, на каждом шаге будет три операции. Сложность двух из них составит $O(n)$, а одной — $O(1)$.

Таким образом, вычислительная сложность сортировки выбором в худшем случае — $O(n^2)$.

Для алгоритмов сортировки учитывают сложность и в лучшем случае. То есть определяют, как долго работает алгоритм на уже отсортированных данных.

В зависимости от задачи и входных данных иногда приходится иметь дело с уже отсортированными массивами. В этом случае важно, чтобы применяемый алгоритм обрабатывал данные как можно быстрее.

Ещё одна сортировка, которая в худшем случае работает за квадратичное время — сортировка вставками. В лучшем случае она работает за $O(n)$. Её используют в алгоритме встроенной сортировки в языке Python. Такая сортировка называется Timsort. Сортировка вставками сочетается в этом алгоритме с сортировкой слиянием. С этим алгоритмом вы познакомитесь в следующих уроках. Благодаря свойству сортировки вставками быстро обрабатывать уже отсортированные последовательности, Timsort использует её, когда находит упорядоченные участки.

Разберемся с пространственной сложностью сортировки выбором.

В прошлом уроке мы говорили о таком свойстве алгоритмов сортировки как устойчивость. Она показывает, может ли поменяться порядок равных элементов после работы алгоритма.

В такой реализации алгоритм устойчивый. Ведь если элемент встречался раньше в массиве, то в результирующем массиве он тоже окажется раньше.

Это верно, если при определении максимума изменяется текущее значение максимального элемента при условии, что найденный элемент строго больше текущего. При использовании нестрогого неравенства (больше либо равно) порядок может поменяться.

Возможно улучшить рассмотренный алгоритм. В текущей формулировке ему требуется $O(n)$ дополнительной памяти. Можно написать алгоритм, который не задействует дополнительную память.

Для этого нужно производить все манипуляции с элементами, используя лишь исходный массив и $O(1)$ дополнительной памяти.

Алгоритм сортировки с таким свойством называется сортировкой на месте.

Код алгоритма сортировки выбором:

Скопировать кодPYTHON
def selection_sort(l):
    for i in range(len(l)-1):
        need_replace = False
        max_elem = l[i]
        for j in range(i, len(l)):
            if l[j] > max_elem:
                need_replace = True
                max_elem = l[j]
                max_pos = j
        if need_replace:
            tmp = l[i]
            l[i] = max_elem
            l[max_pos] = tmp
    return l 

Дополнительный массив не нужен. На шаге $i$ находим в массиве максимум, начиная с позиции $i+1$. Затем сравниваем найденный максимум с элементом на позиции $i$. Если максимум оказывается больше, то они меняются местами.

В начале урока мы рассматривали алгоритм сортировки выбором с использованием $O(n)$ дополнительной памяти. В худшем случае он имеет квадратичную сложность.

Сложность в лучшем случае тоже не изменилась. На каждом из $n$ шагов выбираем наименьший элемент. Сложность этой операции — $O(n)$.

Чтобы убедиться в этом, рассмотрим пример: на вход подан массив $[[a, 2], [b, 2], [c, 5]]$.

Отсортируем его последним алгоритмом по второму элементу — числу.

На первом шаге элементы $[a, 2]$ и $[c, 5]$ поменяются местами. Больше обменов не будет.

Таким образом, порядок элементов $[a, 2]$, $[b, 2]$ изменится по сравнению с их порядком в исходном массиве. Такой алгоритм и называют неустойчивым.

Значения по возрастанию сортируют таким же способом, только выбирают не максимальный, а минимальный элемент в массиве.

В этом уроке вы познакомились с алгоритмом сортировки выбором. Рассмотрели два варианта его реализации. Первый — устойчивый, но требует $O(n)$ дополнительной памяти. Второй вариант реализации неустойчивый, при этом требует всего $O(1)$ дополнительной памяти.

В зависимости от задачи и нужного объёма памяти выбирайте наиболее подходящую реализацию алгоритма.

Вычислительная сложность обеих реализаций в худшем случае $O(n^2)$.

Теперь решите задачи A и B: https://contest.yandex.ru/contest/18899/problems/