Типы квадратичных сортировок в Python с примерами использвания

Одной из самых распространенных задач в программировании является сортировка элементов массива (списка). Задача заключается в том, чтобы дан массив A, содержащий элементы, которые могут быть сравниваемыми (числа, строки, кортежи и т. д.), и переставить их так, чтобы выполнялось условие A[i] ≤ A[i+1] для всех пар соседей.

Для сортировки списков существует множество различных алгоритмов.

Сортировка выбором

Одним из самых простых алгоритмов является сортировка выбором. Суть этого алгоритма в следующем: из списка выбирается наименьший элемент и помещается на позицию с индексом 0. Затем среди оставшихся элементов снова выбирается наименьший, который помещается на позицию с индексом 1, и так далее.

Таким образом, сортировка состоит из двух вложенных циклов. Внешний цикл проходит по индексу i, начиная с 0. Все элементы до индекса i (то есть A[:i]) считаются уже отсортированными.

Теперь необходимо выбрать наименьший элемент из списка A[i:] и поменять его местами с элементом с индексом i.

python  

def SelectionSort(A):

     for i in range(0, len(A) - 1):

          min_idx = i

          for j in range(i + 1, len(A)):

               if A[j] < A[min_idx]:

                    min_idx = j

          A[i], A[min_idx] = A[min_idx], A[i]

Алгоритм можно изменить, убрав сохранение индекса наименьшего элемента: вместо этого при просмотре элементов в срезе A[i:] произвести обмен текущего элемента A[j] с A[i], если A[j] < A[i]:

python  

def SelectionSort(A):

     for i in range(0, len(A) - 1):

          for j in range(i + 1, len(A)):

               if A[j] < A[i]:

                    A[i], A[j] = A[j], A[i]

Оценим сложность этого алгоритма. Если массив содержит n элементов, то для поиска минимума среди n элементов потребуется n операций. Для минимального из n-1 элементов потребуется n-1 операций и так далее. Общее число операций будет равно:

$n + ( n - 1 ) + ( n - 2 ) + \dots + 1 = \frac{ \; \; n \; \; ( \; \; n \; \; + \; \; 1 \; \; ) \; }{2} = O ( n^2 )$ 

Таким образом, сортировка выбором является квадратичным алгоритмом, время выполнения которого пропорционально квадрату размера списка.

Сортировка вставками

Сортировка вставками использует аналогичный инвариант: начальный фрагмент списка (A[:i]) уже отсортирован. Алгоритм устроен для вставки i-го элемента в отсортированную часть. Рассмотрим элемент A[i], который необходимо добавить в уже отсортированную часть.

Вот так выглядит алгоритм:

python  

def InsertionSort(A):

     for i in range(1, len(A)):

          new_elem = A[i]

          j = i - 1

          while j >= 0 and A[j] > new_elem:

               A[j + 1] = A[j]

               j -= 1

          A[j + 1] = new_elem

Теперь оценим сложность алгоритма сортировки вставками. Если массив уже отсортирован, то все элементы останутся на местах, и вложенный цикл не выполнится ни разу, что делает сложность линейной - $O ( n )$. Аналогично, если массив "почти отсортирован" (требуется поменять места лишь несколько близких элементов), сложность также будет линейной.

Таким образом, сложность сортировки вставками зависит от начального состояния массива: в лучшем случае — линейная, в худшем — квадратичная. 

$n + ( n - 1 ) + ( n - 2 ) + \dots + 1 = \frac{ \; \; n \; \; ( \; \; n \; \; + \; \; 1 \; \; ) \; }{2} = O ( n^2 )$

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

Сортировка пузырьком

Сортировка пузырьком основана на простой идее. Если есть два соседних элемента в неправильном порядке (A[i] > A[i + 1]), мы меняем их местами. Повторяя это до тех пор, пока не найдём соседние элементы, находящиеся в неверном порядке, можно отсортировать массив. Но необходимо завершить процесс.

Проходим по всему массиву с левого конца к правому. Если встречаем пару неправильно упорядоченных элементов, меняем их местами. В результате самый большой элемент "всплывёт" в конец -- станет последним. Повторяя этот процесс, второй по величине элемент "всплывёт" в предпоследнюю позицию, и так далее, не затрагивая уже "всплывшие" элементы.

Вот так выглядит алгоритм:

python  

def BubbleSort(A):

     for j in range(len(A) - 1, 0, -1):

          for i in range(0, j):

               if A[i] > A[i + 1]:

                    A[i], A[i + 1] = A[i + 1], A[i]

Сложность этого алгоритма также будет $O ( n^2 )$ . Однако, если запустить пузырьковую сортировку на уже отсортированном массиве, ни одной перестановки не произойдет, но алгоритм выполнит  $O ( n^2 )$  операции. После первого прохода вложенного цикла можно понять, что массив упорядочен, если перестановок не было. Это позволяет оптимизировать алгоритм.

Заведем переменную IsNotOrdered, которая будет True, если массив не упорядочен. Перед внутренним циклом мы установим IsNotOrdered = False, предполагая, что массив уже отсортирован, но если обнаружим пару неупорядоченных элементов, то изменяем IsNotOrdered на True. Внешний цикл продолжается, пока IsNotOrdered верно.

python  

def BubbleSort(A):

     j = len(A) - 1

     IsNotOrdered = True

     while IsNotOrdered:

          IsNotOrdered = False

          for i in range(0, j):

               if A[i] > A[i + 1]:

                    A[i], A[i + 1] = A[i + 1], A[i]

                    IsNotOrdered = True

           j -= 1

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

Существует множество алгоритмов, основывающихся на пузырьковой сортировке. Например, в шейкерной сортировке выполняется поочередный проход слева направо, затем справа налево, а в сортировке Шелла элементы сортируются не по соседям, а по элементам, на большом расстоянии друг от друга, что позволяет более эффективно перемещать элементы.