#13. Быстрая сортировка Хоара | Алгоритмы на Python

Рассказывается об одном из самых популярных алгоритмов быстрой сортировки массивов по Хоару. Приводятся особенности его работы и возможность сортировать непосредственно в исходном массиве. Представлена программа на языке Python.
algorithm-quick-sort.py: github.com/sel...

[@dimakovalenkov7835]

1. рассказать про преимущества сортировки без создания дополнительных списков
2. создать по 3 списка на каждую итерацию(тремя циклами)

[@ДмитрийПименов-ж5ш]

вот пример с сортировкой на месте
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)

[@АлексейЛевицкий-ъ5ф]

@@ДмитрийПименов-ж5ш Спасибо

[@friend1cat]

Спасибо, Сергей.

[@СергейНауменко-ь6н]

Очень доходчиво и интересно спасибо Вам за труды

[@rostislavmalyshev1775]

Спасибо. Как всегда The Best!

[@Яська_Гаспадар_з-пад_Вільні]

Благодарю за материал!

[@deniskrepak]

Очень понятно объясняете, спасибо Вам!

[@mustafinabulhairc-0kn286]

спасибо, большое

[@МихаилПеров-у1ю]

Спасибо!!!

[@sevakvart1111]

Хороший урок

[@zwerg6406]

А почему при сортировке на месте остались 2 последних элемента неотсортированы? [...10, 2]

[@selfedu_rus]

поторопился с перемещением указателя

[@dvkonstantinov]

@@selfedu_rus Нет, дело тут не в указателе. Нужно рекурсию вызывать

[@ЕрвандАгаджанян-в3к]

Спасибо огромное!
А разве Python реализован не на C? Если мы говорим о реализации CPython. Почему вы говорите о C++?
Расскажите, пожалуйста, это интересно.

[@selfedu_rus]

Я, конечно, сам язык не разрабатывал )) но думаю, что его все-таки на С++ делали, т.к. сделать такую вещь без ООП - это подвиг )

[@НикитаХлобыстов-г2й]

а как случайный выбор должен помочь ускорить процесс сортировки. Если случайный выбор будет все попадать на самые малые значения в "гиперсписках", то максимальная сложность все равно будет оN^2

[@selfedu_rus]

Все верно, но вероятность такого события крайне мала.

[@trampika2013]

thanks

[@СергейКондулуков-з9ч]

Не очень понял но интересно.

[@sergeyv1534]

В качестве идеи - дополнить цикл лекций разбором применения метода list.sort() и функции sorted(list) с ключами.

[@selfedu_rus]

Это уже есть: th-cam.com/video/uvlKcOS4OQw/w-d-xo.html

[@sergeyv1534]

@@selfedu_rus Упс, проглядел.

[@alenazhukova8175]

Здесь не происходит inplace сортировки

[@Борис-ц6ю6ж]

без рекурсии тоже работает
def f_sort(l):
if len(l) l[0]]

return left + center + right

[@medencev]

Однократное деление массива на три группы само по себе не отсортирует его (за исключением нескольких частных случаев). Рекурсия является залогом того, что массив поделится на группы равных элементов, которые в дальнейшем будут сгруппированы

[@ymnop9652]

Как и сказали выше, рекурсия сортирует левый и правый массивы, без неё мы можем соединить левый неотсортированный, средний, и правый неотсортированный. пример: [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]

[@dmitrypenzar5229]

быстрой сортировкой это не является (код, что написан). Это штука по логике будет медленнее по-человечески написанной MergeSort

[@selfedu_rus]

Реализация на Python, конечно, медленнее, чем на С++. Здесь объясняется лишь алгоритм сортировки, не более того.

[@dmitrypenzar5229]

@@selfedu_rus проблема не в Python, а в том, как вы на нем написали. У Qsort вся идея в том, что вам НЕ нужно заводить дополнительную память

[@selfedu_rus]

@@dmitrypenzar5229 Это да, я согласен! Ну, идея изложена, реализовать - дело техники )

[@ymnop9652]

@@dmitrypenzar5229Но ведь на Left, MIddle, Rigth память в любом случае уйдёт?

[@AnatoliyDekorstyle]

Вообще конечно реализация "Быстрых сортировок" массива через рекрсию - звучит даже смешно)) максимальная глубина рекурсии (по дефолту ~1000) не позволит сортировать массив с N выше 1000. То есть какие сотни тысяч или милионы)) Скорее упрощенная визуализация алгоритма...

[@ekzzyy]

Разве? Глубина рекурсии в быстрой сортировке будет немного больше чем log2(N), что позволяет сортировать массивы под 2^1000, если брать 1000 за глубину рекурсии.
Если я ошибаюсь, то поясните, пожалуйста.