#13. Быстрая сортировка Хоара | Алгоритмы на Python
Vložit
- čas přidán 4. 03. 2021
- Рассказывается об одном из самых популярных алгоритмов быстрой сортировки массивов по Хоару. Приводятся особенности его работы и возможность сортировать непосредственно в исходном массиве. Представлена программа на языке Python.
algorithm-quick-sort.py: github.com/selfedu-rus/python...
1. рассказать про преимущества сортировки без создания дополнительных списков
2. создать по 3 списка на каждую итерацию(тремя циклами)
вот пример с сортировкой на месте
from random import randint
def partition(array: list, left: int, right: int) -> int:
rand = randint(left, right)
array[rand], array[left] = array[left], array[rand]
x = array[left]
j = left
for i in range(left + 1, right + 1):
if array[i] None:
if left < right:
m = partition(array, left, right)
quick_sort(array, left, m - 1)
quick_sort(array, m + 1, right)
@@user-oj9pb3bv5w Спасибо
Очень доходчиво и интересно спасибо Вам за труды
Очень понятно объясняете, спасибо Вам!
Спасибо, Сергей.
Спасибо. Как всегда The Best!
Благодарю за материал!
спасибо, большое
Спасибо!!!
Хороший урок
thanks
Спасибо огромное!
А разве Python реализован не на C? Если мы говорим о реализации CPython. Почему вы говорите о C++?
Расскажите, пожалуйста, это интересно.
Я, конечно, сам язык не разрабатывал )) но думаю, что его все-таки на С++ делали, т.к. сделать такую вещь без ООП - это подвиг )
Не очень понял но интересно.
А почему при сортировке на месте остались 2 последних элемента неотсортированы? [...10, 2]
поторопился с перемещением указателя
@@selfedu_rus Нет, дело тут не в указателе. Нужно рекурсию вызывать
Здесь не происходит inplace сортировки
а как случайный выбор должен помочь ускорить процесс сортировки. Если случайный выбор будет все попадать на самые малые значения в "гиперсписках", то максимальная сложность все равно будет оN^2
Все верно, но вероятность такого события крайне мала.
В качестве идеи - дополнить цикл лекций разбором применения метода list.sort() и функции sorted(list) с ключами.
Это уже есть: czcams.com/video/uvlKcOS4OQw/video.html
@@selfedu_rus Упс, проглядел.
без рекурсии тоже работает
def f_sort(l):
if len(l) l[0]]
return left + center + right
Однократное деление массива на три группы само по себе не отсортирует его (за исключением нескольких частных случаев). Рекурсия является залогом того, что массив поделится на группы равных элементов, которые в дальнейшем будут сгруппированы
Как и сказали выше, рекурсия сортирует левый и правый массивы, без неё мы можем соединить левый неотсортированный, средний, и правый неотсортированный. пример: [3,2,5,8,7,1] где значение с которым сравниваем - 5 получим L = [3, 2, 1] M = [5] R = [8, 7], L + M + R = [3, 2, 1, 5, 8, 7]
быстрой сортировкой это не является (код, что написан). Это штука по логике будет медленнее по-человечески написанной MergeSort
Реализация на Python, конечно, медленнее, чем на С++. Здесь объясняется лишь алгоритм сортировки, не более того.
@@selfedu_rus проблема не в Python, а в том, как вы на нем написали. У Qsort вся идея в том, что вам НЕ нужно заводить дополнительную память
@@dmitrypenzar5229 Это да, я согласен! Ну, идея изложена, реализовать - дело техники )
@@dmitrypenzar5229Но ведь на Left, MIddle, Rigth память в любом случае уйдёт?
Вообще конечно реализация "Быстрых сортировок" массива через рекрсию - звучит даже смешно)) максимальная глубина рекурсии (по дефолту ~1000) не позволит сортировать массив с N выше 1000. То есть какие сотни тысяч или милионы)) Скорее упрощенная визуализация алгоритма...
Разве? Глубина рекурсии в быстрой сортировке будет немного больше чем log2(N), что позволяет сортировать массивы под 2^1000, если брать 1000 за глубину рекурсии.
Если я ошибаюсь, то поясните, пожалуйста.