Быстрая сортировка в python. Quick sort in Python. Recursive sorting algorithms

Стать спонсором канала и получить доступ к дополнительным материалам по Python

Сортировка слиянием в python

Условие задачи

Рекурсия в Python. Рекурсивная функция

Курс по основам python на Степике

Записывайся на курс на Stepic по ООП, где найдешь много практических задач

Если кому нужна помощь, предлагаю индивидуальные занятия. Подробнее пишите в личку в вк

В данном группе можете найти информацию о новых видео и задать вопросы

[dimitrilarios]

Отличный преподаватель. Алгоритмы - в плейлист.

[bqukchm]

Спасибо, Егор, по моему самое адекватное объяснение. И слушать приятно)).

[vladislav.ivanov]

Спасибо, наконец-то разобрался с рекурсией

[gbjdkbw]

Спасибо! Наконец-то понял. Отдельная благодарность за демонстрацию работы с отладчиком.

[spartanec_channel]

_Большое спасибо за урок!_ Этот понятнее, чем предыдущий)

[uyndwbo]

Лучшее объяснение что нашел на ютубе. Благодарю

[ymnop]

Уф, целых три цикла перебора вместо одного, супер эффективно:D

[evollt]

красавчик. Объяснил все на понятном языке. Недавно начал читать книгу:"грокаем алгоритмы", вот и не понял алгоритм быстрой сортировки, а ты все прям разжевал как надо. Подписочка оформлена!

[arxxximed]

А в целом очень хорошо и понятно объясняете

[rentbest]

Спасибо за видео. Я проверил два способа:
1) с использованием метода filter
2) генератор списка через [el for el in arr if el (<, >, ==) pivot]
Вывод: второй метод быстрее, так как не идет вызов функций (а такая операция в питоне происходит не слишком быстро). Возможно, в другом языке ситуация будет иная.

[sergeyl]

elem = s[len(s)//2] вот так должно быть. А иначе при выборе элементов > 2 ошибку выбивает

[ЧувакИзКосмоса]

скажите, товарищи, а такого рода многократные пробежки не тратят ли больше памяти и времени? я понимаю, это генераторы, однако в каждом следующем генераторе мы проверяем каждый элемент повторно! не эффективнее ли запустить один цикл и в нём проверять величину переменной?
for i in lst:
if i < base:
less.append(i)
elif i > base:
bigger.append(i)
else:
centre.append(i)

или получается одно и то же, ведь мы каждый элемент в худшем случае проверяем дважды?

[codetoday]

Яке це швидке сортування якщо ви створюєте нові масиви. Тобто відміність швидкого сортуввння від сортування злиттям зникає. (їх відміність в просторовій суладності)

[arxxximed]

Вы создаете на каждой итерации рекурсии новые списки- при больших начальных списках память уйдет очень быстро. Изначальный алгоритм быстрой сортировки - эта работа с указателями.

[obricto]

В "Грохаем алгоритмы" есть фраза - "Если вы всегда
будете выбирать опорным элементом случайный элемент в массиве, бы­
страя сортировка в среднем завершится за время О(п log п). " - при этом результирующий массив отличается по количеству элементов от искомого (по вашей программе)((( Как это исправить??

[braininasquare]

Через фильтр большой список становится далеко не быстрым для сортировки

[Nikbleat]

Такой вопрос, несколько глупый может быть, но для меня пока актуальный. Почему алгоритм является более быстрым, если в обычной сортировке, методом перебора всех элементов и перестановки позиций, так же проверяется каждый элемент, но в этом методе ещё больше действий кроме перебора элементов? И это ещё не говоря о вложенности, которая при огромных массивах вообще может нехило занять память.

[vetenskap]

У меня вопрос возник, а почему все эти супер пупер алгоритмы изначально не встроить в языке программирования в качестве встроенных функций ? Почему нужно свои костыли делать ?

[swukxui]

Вы в самом начале ролика сказали что можно брать любой элемент. Это явно ошибка потому что при увеличении размеров списка и например если мы берем первый элемент - скорость вашей работы будет заведомо меньше чем при серединном элементе. Это можно явно заметить при быстрой сортировке с разбиением дейкстры. Если в этом случае вы берете первый элемент - у вас идет сильный упадок скорости. Этот момент нужно подметить и учесть что каждый элемент должен быть - element = array[len(array) // 2] - вот в таком случае на каждой итерации будет решать за nlogn
Учтите это после просмотра!

[tumka]

сортировка летит на массиве из равных элементов