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

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

[@dimakovalenkov7835]

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

[@user-oj9pb3bv5w]

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

@@user-oj9pb3bv5w Спасибо

[@user-ym3yt1uq7s]

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

[@deniskrepak]

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

[@rostislavmalyshev1775]

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

[@friend1cat]

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

[@user-ji5wf5ke4b]

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

[@kat_katchinskiy]

на 9:53 не понял почему в конце двойка если массив отсортирован -_-

[@YbisZX]

Это на первой итерации. Нужно столько таких проходов пока не будет ни одной перестановки.

[@mustafinabulhairc-0kn286]

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

[@user-yp6yv2ub2u]

Спасибо!!!

[@trampika2013]

thanks

[@sevakvart1111]

Хороший урок

[@zwerg6406]

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

[@selfedu_rus]

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

[@dvkonstantinov]

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

[@user-ee1lx1pe7n]

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

[@selfedu_rus]

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

[@user-qh5fr3yo1w]

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

[@user-qd2yy7nw5m]

Написана сортировка с использованием памяти на создание дополнительных массивов. При том, что ранее было сказано, что одно из главных преимуществ быстрой сортировки - это минимальное задействование памяти. Я, конечно, понимаю, что так гораздо проще для восприятия, но, блин, этого же недостаточно. У меня просто накипело - я уже кучу ресурсов пересмотрел и везде объясняют, как попало. Это же один из самых важных алгоритмов, почему нельзя разобрать его нормально. Тем более он используется в стандартной сортировке Python. Сергей, вы очень хорошо объясняете, огромное вам спасибо за ваши труды. Многое изучил по вашим видео, вы сильно выделяетесь на общем фоне. Но этот плейлист с алгоритмами не самый удачный. Я понимаю, что тема объемная и сложная, но она основополагающая. И мне непонятно, почему даже вы не смогли нормально объяснить такие важные вещи. Если даже вы не смогли, то кто тогда сможет? :)

[@sergeyv1534]

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

[@selfedu_rus]

Это уже есть: kzbin.info/www/bejne/q6fPfJaFiJmCh9k

[@sergeyv1534]

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

[@user-ry2su4jo2l]

без рекурсии тоже работает 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. То есть какие сотни тысяч или милионы)) Скорее упрощенная визуализация алгоритма...

[@ekzzy9054]

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