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

[@dimitrilarios2667]

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

[@rentbest]

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

[@ТигранСаркисян-ф3и]

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

[@ДмитрийСмолянников]

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

[@TIMSYSTEM]

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

[@barbaferam4762]

Я использую combosort годами, он прекрасно вписьівается в целочисленную математику, и не изпользует много оперативки и стека.

[@vladislav.ivanov]

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

[@evollt]

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

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

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

[@МагомедНурмагомедов-л3п]

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

[@doloidiktatorov]

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

[@arxxximed]

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

[@trahar]

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

[@arxxximed]

@@trahar отчасти согласен с вашим рассуждением. Отчасти нет. 1. По поводу лучшего способа - лучший способ на сегодняшний момент - это как раз пользоваться встроенными средствами языка. 2. Здесь мы разбираем классические алгоритмы. Соответственно было бы не плохо указать плюсы и минусы этих алгоритмов. Плюс Quick search как раз таки в том, что он должен работать с одним списком как объект, не создавая новых, и не захламляя память. Автор очень хорошо и понятно объяснил суть работы алгоритма на примере создания списков... Но наверное стоило бы потом и перейти на классическую его реализацию... С объяснением и разбором.

[@trahar]

@@arxxximed это да! так-то и нужно

[@dimakovalenkov7835]

+ каждый раз список перебирается по 3 раза по итогу сортировка замедляется в 3 раза теперь это медленная сортировка = )

[@userr19194]

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

[@sergeyl1223]

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

[@ymnop9652]

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

[@arxxximed]

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

[@begula_chan]

Спасибо!

[@doordie6341]

есть разница в скорости выполнения алгоритма исходя из того какой элемент брать за базовый?

[@codetoday1055]

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

[@АлексейЮдин-и9д]

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

[@ГеоргийЗагорский-э5к]

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

[@begula_chan]

А выбор рандомного опорного элемента тоже будет занимать nlogn?

[@ИгорьСухов-т6щ]

Ты хорош !)

[@braininasquare2199]

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

[@Tamagochi4x4]

Что это за курс на степике?

[@vivacuba1990]

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

[@edgull_tlt]

Спасибо

[@Nikbleat]

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

[@ҒалымжанБерікұлы]

из-за рекурсии думаю

[@MrFrimko]

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

[@Strongflight]

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

[@Strongflight]

def quick_sort(s): if len(s) > 1: elem = s[0] left = list(filter(lambda x: x < elem, s)) center = [i for i in s if i == elem] right = list(filter(lambda x: x > elem, s)) return quick_sort(left) + center + quick_sort(right) else: return s

[@obe1313]

зачем 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)

[@arxxximed]

так был же пример, а если ты выбрал в качестве ключевого элемента семерку, а у тебя в списке 30 семерок? Остальные семерки в какую сторону пойдут в right или left?

[@obe1313]

Al Zhuch делаешь тогда меньше либо равно в left, либо наоборот в right

[@arxxximed]

@@obe1313 И можешь столкнуться с бесконечным циклом )))))) Ты попробуй написать эту прогу

[@gameplays_from_hdd]

@@arxxximed, каким образом там бесконечный цикл появляется?

[@ГвидоПитон]

программирование не твое, иди в начальники)

[@tumka6988]

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

[@vetenskap1573]

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

[@MrFrimko]

так они есть. алгоритмы надо изучать не для того что их самому писать, а что понимать как работает то что уже написано

[@Al-en6nj]

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

[@trahar]

можешь отписаться от канала и больше не смотреть никаких материалов на тему сортировки, раз такой умник

[@justalpaca4943]

Ахахах, программист нашелся... Задача не отсортировать что-то а понять принцип работы данного алгоритма. Как минимум по твоему комментарию можно прийти к выводу что программирование это не твоё. Не знаю, займись чем-нибудь другим.

[@WinchesterD]

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

[@Nikbleat]

Этим вопросом ты должен был озадачиться ещё перед изучением алгоритмов

[@ymnop9652]

Нет универсального алгоритма, и не смотря на то, что в питоне умный сортировщик и он использует несколько алгоритмов, возможна ситуация когда тебе для оптимального решения текущей задачи нужен конкретный алгоритм сортировки, для этого нужно знать алгоритмы сортировки, их слабые и сильные места. А тут задачу изменили нужный алгоритм из гугла не работает, его нужно чуть изменить под специфику задачи, скажем сделать не устойчивым и ещё что-то там. Теперь тебе нужно знать не только что существует такой алгоритм, но и как он работает и что нужно изменить в нём для решения проблемы. Алгоримы это история про эффективность, понимая как их делают такими быстрыми можно в принципе писать более чистый код, который легче читать ещё он будет быстрее и в нём не будет лишних условий\сомнительных решений. И даже решая другую задачу принцип решения алгоритмов может быть полезен: придумай наивное решение, разбей задачу, найди бутылочное горлышко, сделай рефакторинг -> повторяй до оптимального результата.

[@CRESHT]

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

[@fugas6258]

*ваавав*

[@nicholasspezza9449]

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

[@zhanibeksapakov9084]

спасибо