Квадратичные алгоритмы сортировки

Под квадратичными алгоритмами сортировки понимаются такие алгоритмы, временная сложность которых выражается как O(n²). Т.е. если нам на вход дан массив длинной 10, то мы выполним 100 операций для того, чтобы его отсортировать.

Во всех нижеприведенных переменных нет выражения return, т.к. функции сортируют переданные им массивы «на месте». И в случае, когда return не указан, то функция вернет None.

Сортировка вставками (insertion sort)

Джуну прилетела важная задача по сортировке массива, но он, к сожалению, не знает про встроенные методы сортировки в Питоне и знаком только с тем, как можно сортировать вставками.

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

numbers = [5, 6, 1, 100, 12, 44, 55, 23, 33, 11, 99, 12, 66]

def insertion_sort(numbers):
    numbers_length = len(numbers)
    for i in range(1, numbers_length):
        k = i
        while k > 0 and numbers[k-1] > numbers[k]:
            numbers[k], numbers[k-1] = numbers[k-1], numbers[k]
            k -= 1

insertion_sort(numbers)
print(f'result: {numbers}')
# result: [1, 5, 6, 11, 12, 12, 23, 33, 44, 55, 66, 99, 100]

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

Внутри функции insertion_sort() первым делом объявляется переменная numbers_length, которая содержит в себе длину массива. Далее в цикле for от первого элемента до последнего включительно мы начинаем выполнять манипуляции по перестановке чисел.

Переменная k хранит индекс элемента, который мы собераемся передвинуть на другую позицию, в случае если он больше предыдущего. После объявления переменной k мы создаем цикл while с условием «пока k больше нуля и предыдущий элемент массива больше текущего».
И в блоке инструкций уже описываем, что мы хотим сделать — а хотим мы поменять текущий элемент с предыдущим, а затем уменьшить значение k на единицу.

По сути алгоритм сравнивает попарно элементы, которые стоят рядом и затем их меняет местами. Например, если бы у нас был массив [5, 4, 3, 2, 1], то на последней итерации цикла for мы бы протащили единицу с последней позиции на нулевую попутно сравнивая с каждый предыдущим элементом.

Для массива [5, 4, 3, 2, 1] это выглядело бы так:

На первой итерации цикла for сравнимаем 4 и 5 — 4 меньше 5, поэтому меняем их местами и получаем массив [4, 5, 3, 2, 1].
На второй итерации сравниваем 3 с предыдущими элементами, пока 3 не встанет на нулевую позицию. Когда условия цикла while станут ложными у нас будет массив [3, 4, 5, 2, 1].
На третьей итерации сравниваем 2 с предыдущими элементами и получаем массив [2, 3, 4, 5, 1].
И на последней итерации мы «тащим» единицу на самую первую позицию поочередно меняя её с предыдущими элементами и получаем отсортированный массив [1, 2, 3, 4, 5].

Сортировка методом выбора (selection sort | choise sort)

Функция сортировки выбором выглядит следующим образом:

numbers = [5, 4, 3, 2, 1]
numbers_length = len(numbers)

def selection_sort(numbers):
    for i in range(numbers_length-1):
        for k in range(i+1, len(numbers)):
            if numbers[k] < numbers[i]:
                numbers[k], numbers[i] = numbers[i], numbers[k]

selection_sort(numbers)
print(f'result: {numbers}')
# result: [1, 2, 3, 4, 5]

В данной сортировке мы идем по порядку от начала до предпоследнего элемента и сравниваем с «впередистоящими» элементами. Первая итерация внешнего цикла for для массива [5, 4, 3, 2, 1] выглядит так:

Берем элемент с индексом 0 и сравниваем его с элементом под индексом 1 — 4 < 5, поэтому меняем их местами и получаем массив [4, 5, 3, 2, 1].
На нулевом индексе у нас теперь стоит число 4, сравниваем с элементом под индексом 2 — 3 > 4, поэтому меняем местами. Получаем массив [3, 5, 4, 2, 1].
Теперь сравниваем число 3 с элементом под индексом 3. Два меньше трех, поэтому меняем их местами. Получаем массив [2, 5, 4, 3, 1].
Тут можно догадаться, что будет дальше 🙂 Снова сравниваем число под индексом 0 с индексом k+1. На этот раз k равен 4, где у нас стоит число 1. Единица отправляется на нулевую позицию, а двойка отправляется в конец. Получаем массив [1, 5, 4, 3, 2].

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

Сортировка пузырьком (bubble sort)

numbers = [5, 4, 3, 2, 1]
numbers_length = len(numbers)

def bubble_sort(numbers):
    for i in range(1, numbers_length):
        for k in range(numbers_length-i):
            if numbers[k] > numbers[k+1]:
                numbers[k], numbers[k+1] = numbers[k+1], numbers[k]

print(f'result: {numbers}')
# result: [1, 2, 3, 4, 5]

Сортировка пузырьком чем-то похожа и на сортировку вставками и на сортировку выбором.
Здесь мы на каждой итерации «толкаем» наибольший элемент вперед, пока он не встанет на своё место.

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