Время прочтения: 5 мин.

Изучение алгоритмов и понимание заложенных в них принципов работы является неотъемлемой частью обучения. Многие алгоритмы уже реализованы в библиотеках, но для оптимизации скорости выполнения или добавление признаков важно знать, что находится «под капотом» и как реализовать что-то с нуля. Рассмотрим алгоритмы с такой структурой данных как списки: квадратичные сортировки и сортировки, работающие по принципу, разделяй и властвуй, а также проверку на отсортированность списка.

Все сортировки будем тестировать на одним и тех же входных данных. Сгенерируем список и используем метод shuffle встроенной библиотеки random:

import random
numbers = list(range(1, 10**4))
random.shuffle(numbers)

Для определения времени выполнения сортировки в jupyter notebook нужно указать в начале ячейки магический метод %%time либо воспользуйтесь декоратором для .py расширения:

import time

def timer(func):
    def wrapper(*args, **kwargs):
        before = time.monotonic()
        retval = func(*args, **kwargs)
        after = time.monotonic()- before
        print("Function {}: {} seconds".format(func.__name__, after))
        return retval
    return wrapper

Перед каждой функцией, время выполнения которой вы хотите вычислить добавьте строчку:

@timer

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

Количество операций, которое требуется для сортировки примерно O(N**2). 

Про big O notation можно почитать здесь.

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

%%time
def insert_sort(A):
    lst = A.copy()
    N = len(lst)
    for top in range(1, N):
        k = top
        while k > 0 and lst[k-1] > lst[k]:
            lst[k], lst[k-1] = lst[k-1], lst[k]
            k -= 1
    return lst


print(insert_sort(numbers))

Время выполнения сортировки: 6.79 сек.

Инвариант у каждой сортировки свой. Принцип работы сортировки вставками: проверяем элементы слева-направо начиная со второго и смотрим больше ли он предыдущего, если да, оставляем на месте, если элемент меньше предыдущего, берем его и тащим налево до тех пор, пока не встретим элемент меньше, чем он.

Сортировка списка выбором.

%%time
def choice_sort(A:list):
    """
    Сортировка списка А выбором. Бежим по циклу и ищем того,
    кто меньше нашего минимума и меняем местами.
    """
    lst = A.copy()
    N = len(lst)
    for pos in range(N-1):              
        for k in range(pos+1, N):
            if lst[k] < lst[pos]:
                lst[k], lst[pos] = lst[pos], lst[k]
    return lst

print(choice_sort(numbers))

Время выполнения сортировки: 5.04 сек.

Первый элемент в начальной позиции принимаем за самый маленький и бежим по списку слева направо и ищем того, кто меньше его, когда нашли меняем местами, дальше уже не смотрим на первую позицию считая, что элемент уже на своем месте (этот момент реализован в цикле как —  начни с range(pos+1, N) и так с каждым кроме последнего, т.к. он сам окажется на своем месте.

Пузырьковая сортировка списка.

%%time
def bubble_sort(A):
    lst = A.copy()
    N = len(lst)
    for bypass in range(1, N):
        for k in range(0, N-bypass):
            if lst[k] > lst[k+1]:
                lst[k], lst[k+1] = lst[k+1], lst[k]
    return lst

print(bubble_sort(numbers))

Время выполнения сортировки: 7.42 сек.

Производится проход по списку слева направо и, если текущий элемент меньше предыдущего, то они меняются местами. Таким образом самый большой элемент подобно пузырьку всплывет в самую последнюю позицию. Далее, используя отсечение в цикле N-bybass, исключаем возможность проверки тех элементов, которые уже “всплыли наверх”.

Превосходное объяснение работы сортировок вы можете посмотреть в  лекции.

Рекуррентные сортировки.

Быстрая сортировка и сортировка слиянием работает по принципу “разделяй и властвуй”. В отличие от квадратичных сортировок они выполняются с логарифмической сложностью.

Сортировка Тома Хоара (Quick sort).

Обычно на случайных выборках она работает W(N *log2N), а иногда O(N**2). Сортирующие действия выполняются на прямом ходу рекурсии. Дополнительная память не требуется.

Делаем явную копию списка numbers т.к. сортировка изменяет входной список напрямую:

list_for_test = numbers.copy()

Сортировка:

%%time
def hoar_sort(A):
    if len(A) <= 1:
        return
    barrier = A[0]
    L = []
    M = []
    R = []
    for x in A:
        if x < barrier:
            L.append(x)
        elif x == barrier:
            M.append(x)
        else:
            R.append(x)
    hoar_sort(L)
    hoar_sort(R)
    k = 0
    for x in L+M+R:
        A[k] = x
        k += 1
        

hoar_sort(list_for_test)

print(list_for_test)

Время выполнения сортировки: 0.30 сек.

Берем первый элемент и считаем его барьером, далее сортируем список, т.е. те, кто меньше его, идут в левый список, те, кто больше, идут в правый список, а равные ему идут в средний список. Передаем каждый наш фрагмент снова в функцию, тем самым реализовав рекурсию, пока не сработает крайний случай, что значит длина списка равна единице или нулю, и далее соединяем три получившихся части: L, M, R в список A.

Сортировка слиянием.

На любых входных данных работает O(N*log2N). Сортировка выполняется на обратном ходу рекурсии. Требуется дополнительная память.

list_for_test = numbers.copy()

%%time
def merge_sort(A):  
    if len(A) <= 1:
        return
    middle = len(A) // 2
    L = [A[i] for i in range(0, middle)]
    R = [A[i] for i in range(middle, len(A))]
    merge_sort(L)
    merge_sort(R)
    C = merge(L, R)
    for i in range(len(A)):
        A[i] = C[i]


def merge(A:list, B:list):  
    C = [0] * (len(A) + len(B))
    i = 0
    k = 0
    n = 0
    while i < len(A) and k < len(B):
        if A[i] <= B[k]:
            C[n] = A[i]
            i += 1
            n += 1
        else:
            C[n] = B[k]
            k += 1
            n += 1
    while i < len(A):
        C[n] = A[i]
        i += 1
        n += 1
    while k < len(B):
        C[n] = B[k]
        k += 1
        n += 1
    return C

merge_sort(list_for_test)
print(list_for_test)

Время выполнения сортировки: 0.60 сек.

Как выполняется сортировка: рекурсивно делим списки пополам на левую и правую части, далее, встретив крайний случай (длина списка <=1) на обратном ходу рекурсии, эти пары половинок попадают в функцию merge. В ней сначала создается новый список С, в который далее вливаются значения из половинок слева направо. Функция merge возвращает список С, значения которого уже в отсортированном виде попадают в цикле в список А.

Проверка того, что список отсортирован за O(len(A)).

def check_sorted(A:list, ascending=True):
    flag = True
    s = 2*int(ascending)-1
    for i in range(0, len(A)-1):
        if s*A[i] > s*A[i+1]:
            flag = False
            break
    return flag

test = [1, 2, 3, 4, 5, 6, 7]
check_sorted(test)

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

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