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

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

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

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

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

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

Это уже есть: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-uvlKcOS4OQw.html

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

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

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

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

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

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

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

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