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

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

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

Ни про сложность по времени не рассказал, ни по памяти.

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

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

спасибо

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

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

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

Спасибо!

Егорка, у тебя с головушкой-то все в порядке, нет? Какая лямбда? Какой фильтр? Мы это не проходили в рамках курса, ты вообще свою филькину грамоту на Степике сам-то видел? Или слепо лепишь совсем не думая, что получится? Позорище, отвратительный курс, автор абсолютно не понимает как построить принцип обучения и вся суть его пребывания на Степике это тешить ЧСВ и впарить какую-то дичь под видом обучения Питону.
Влепил видео дизлайк! Дизлайк теме на Степике!

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

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

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

Объяснение хорошее, но код кошмар для новичков. Какая-то лябда, for - просто ужас. Как научиться сортировке если код не понятен ?

ваавав

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

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

Ты хорош !)

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

Команда на выход приводит к ошибке.
Немного переделал:

Эх, кто бы ещё объяснил, зачем знать алгоритмы сортировки разработчику на Python, если встроенный метод прекрасно справляется с задачей.

Спасибо

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

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

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

ясно и понятно...

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

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

зачем center, если left всегда меньше elem, а right всегда больше elem?
можно center убрать, и возвращать return qiucksort(left) + [elem] + qiucksort(right)

def qiuck_sort(s):
if len(s) < 2:
return s
else:
elem = s[0]
left = [i for i in s[1:] if i < elem]
right = [i for i in s[1:] if i > elem]
return qiuck_sort(left) + [elem] + qiuck_sort(right)

Огромное спасибо за алгоритмы.

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

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

Выглядит как магия!

Быстрая сортировка ---> sort(....)