{"id":14277,"url":"\/distributions\/14277\/click?bit=1&hash=17ce698c744183890278e5e72fb5473eaa8dd0a28fac1d357bd91d8537b18c22","title":"\u041e\u0446\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u043b\u0438\u0442\u0440\u044b \u0431\u0435\u043d\u0437\u0438\u043d\u0430 \u0438\u043b\u0438 \u0437\u043e\u043b\u043e\u0442\u044b\u0435 \u0443\u043a\u0440\u0430\u0448\u0435\u043d\u0438\u044f","buttonText":"\u041a\u0430\u043a?","imageUuid":"771ad34a-9f50-5b0b-bc84-204d36a20025"}
NTA

Подборка алгоритмов для изучения языка Python

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

Все сортировки будем тестировать на одним и тех же входных данных. Сгенерируем список и используем метод 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.

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

24 показа
8.7K открытий
0
2 комментария
Андрей

Очень полезная публикация! Спасибо автору!

Ответить
Развернуть ветку
Никита Стокалюк

Спасибо !

Ответить
Развернуть ветку
Написать комментарий...
-1 комментариев
Раскрывать всегда