Быстрая сортировка в python. Quick sort in Python. Recursive sorting algorithms
ฝัง
- เผยแพร่เมื่อ 7 ธ.ค. 2020
- Стать спонсором канала и получить доступ к дополнительным материалам по Python
/ @egoroffchannel
boosty.to/egoroff_channel
/ artem_egorov
Сортировка слиянием в python
• Сортировка слиянием в ...
Условие задачи
stepik.org/edit-lesson/372095...
Рекурсия в Python. Рекурсивная функция
• 42 Рекурсия в Python. ...
stepik.org/course/63085/syllabus
Курс по основам python на Степике
stepik.org/course/72969/promo
Записывайся на курс на Stepic по ООП, где найдешь много практических задач
Если кому нужна помощь, предлагаю индивидуальные занятия. Подробнее пишите в личку в вк
artem_egoroff
python.study
В данном группе можете найти информацию о новых видео и задать вопросы
Отличный преподаватель. Алгоритмы - в плейлист.
Спасибо, Егор, по моему самое адекватное объяснение. И слушать приятно)).
Спасибо, наконец-то разобрался с рекурсией
Выглядит как магия!
Спасибо! Наконец-то понял. Отдельная благодарность за демонстрацию работы с отладчиком.
_Большое спасибо за урок!_ Этот понятнее, чем предыдущий)
Огромное спасибо за алгоритмы.
Спасибо за видео. Я проверил два способа:
1) с использованием метода filter
2) генератор списка через [el for el in arr if el (, ==) pivot]
Вывод: второй метод быстрее, так как не идет вызов функций (а такая операция в питоне происходит не слишком быстро). Возможно, в другом языке ситуация будет иная.
Уф, целых три цикла перебора вместо одного, супер эффективно:D
Лучшее объяснение что нашел на ютубе. Благодарю
А в целом очень хорошо и понятно объясняете
Спасибо!
красавчик. Объяснил все на понятном языке. Недавно начал читать книгу:"грокаем алгоритмы",вот и не понял алгоритм быстрой сортировки,а ты все прям разжевал как надо. Подписочка оформлена!
elem = s[len(s)//2] вот так должно быть. А иначе при выборе элементов > 2 ошибку выбивает
ясно и понятно...
Ты хорош !)
Вы создаете на каждой итерации рекурсии новые списки- при больших начальных списках память уйдет очень быстро. Изначальный алгоритм быстрой сортировки - эта работа с указателями.
он изначально сказал "один из способов быстрой сортировки", что это подразумевает под собой?!?!? способ на то и способ, что подходит для определённых ситуаций, когда список маленький - пожалуйста, пользуйся! большой?! ищи идею лучше!
@@trahar отчасти согласен с вашим рассуждением. Отчасти нет.
1. По поводу лучшего способа - лучший способ на сегодняшний момент - это как раз пользоваться встроенными средствами языка.
2. Здесь мы разбираем классические алгоритмы. Соответственно было бы не плохо указать плюсы и минусы этих алгоритмов. Плюс Quick search как раз таки в том, что он должен работать с одним списком как объект, не создавая новых, и не захламляя память. Автор очень хорошо и понятно объяснил суть работы алгоритма на примере создания списков... Но наверное стоило бы потом и перейти на классическую его реализацию... С объяснением и разбором.
@@arxxximed это да! так-то и нужно
+ каждый раз список перебирается по 3 раза
по итогу сортировка замедляется в 3 раза
теперь это медленная сортировка = )
спасибо
скажите, товарищи, а такого рода многократные пробежки не тратят ли больше памяти и времени? я понимаю, это генераторы, однако в каждом следующем генераторе мы проверяем каждый элемент повторно! не эффективнее ли запустить один цикл и в нём проверять величину переменной?
for i in lst:
if i < base:
less.append(i)
elif i > base:
bigger.append(i)
else:
centre.append(i)
или получается одно и то же, ведь мы каждый элемент в худшем случае проверяем дважды?
Спасибо
В "Грохаем алгоритмы" есть фраза - "Если вы всегда
будете выбирать опорным элементом случайный элемент в массиве, бы
страя сортировка в среднем завершится за время О(п log п). " - при этом результирующий массив отличается по количеству элементов от искомого (по вашей программе)((( Как это исправить??
Яке це швидке сортування якщо ви створюєте нові масиви. Тобто відміність швидкого сортуввння від сортування злиттям зникає. (їх відміність в просторовій суладності)
Такой вопрос, несколько глупый может быть, но для меня пока актуальный. Почему алгоритм является более быстрым, если в обычной сортировке, методом перебора всех элементов и перестановки позиций, так же проверяется каждый элемент, но в этом методе ещё больше действий кроме перебора элементов? И это ещё не говоря о вложенности, которая при огромных массивах вообще может нехило занять память.
из-за рекурсии думаю
количество этих самых переборов другое.
попробуй руками отсортировать список пузырьком и квиксортом, считая количество сравнений и перестановок.
что бы разница была видна, список побольше взять, 7+ элементов
Вы в самом начале ролика сказали что можно брать любой элемент. Это явно ошибка потому что при увеличении размеров списка и например если мы берем первый элемент - скорость вашей работы будет заведомо меньше чем при серединном элементе. Это можно явно заметить при быстрой сортировке с разбиением дейкстры. Если в этом случае вы берете первый элемент - у вас идет сильный упадок скорости. Этот момент нужно подметить и учесть что каждый элемент должен быть - element = array[len(array) // 2] - вот в таком случае на каждой итерации будет решать за nlogn
Учтите это после просмотра!
А выбор рандомного опорного элемента тоже будет занимать nlogn?
У меня вопрос возник, а почему все эти супер пупер алгоритмы изначально не встроить в языке программирования в качестве встроенных функций ? Почему нужно свои костыли делать ?
так они есть. алгоритмы надо изучать не для того что их самому писать, а что понимать как работает то что уже написано
Через фильтр большой список становится далеко не быстрым для сортировки
сортировка летит на массиве из равных элементов
зачем 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)
так был же пример, а если ты выбрал в качестве ключевого элемента семерку, а у тебя в списке 30 семерок?
Остальные семерки в какую сторону пойдут в right или left?
Al Zhuch делаешь тогда меньше либо равно в left, либо наоборот в right
@@obe1313 И можешь столкнуться с бесконечным циклом
)))))) Ты попробуй написать эту прогу
@@arxxximed, каким образом там бесконечный цикл появляется?
Эх, кто бы ещё объяснил, зачем знать алгоритмы сортировки разработчику на Python, если встроенный метод прекрасно справляется с задачей.
Этим вопросом ты должен был озадачиться ещё перед изучением алгоритмов
Нет универсального алгоритма, и не смотря на то, что в питоне умный сортировщик и он использует несколько алгоритмов, возможна ситуация когда тебе для оптимального решения текущей задачи нужен конкретный алгоритм сортировки, для этого нужно знать алгоритмы сортировки, их слабые и сильные места. А тут задачу изменили нужный алгоритм из гугла не работает, его нужно чуть изменить под специфику задачи, скажем сделать не устойчивым и ещё что-то там. Теперь тебе нужно знать не только что существует такой алгоритм, но и как он работает и что нужно изменить в нём для решения проблемы.
Алгоримы это история про эффективность, понимая как их делают такими быстрыми можно в принципе писать более чистый код, который легче читать ещё он будет быстрее и в нём не будет лишних условий\сомнительных решений. И даже решая другую задачу принцип решения алгоритмов может быть полезен: придумай наивное решение, разбей задачу, найди бутылочное горлышко, сделай рефакторинг -> повторяй до оптимального результата.
Команда на выход приводит к ошибке.
Немного переделал:
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
*ваавав*
Быстрая сортировка ---> sort(....)
можешь отписаться от канала и больше не смотреть никаких материалов на тему сортировки, раз такой умник
Ахахах, программист нашелся... Задача не отсортировать что-то а понять принцип работы данного алгоритма. Как минимум по твоему комментарию можно прийти к выводу что программирование это не твоё. Не знаю, займись чем-нибудь другим.
Объяснение хорошее, но код кошмар для новичков. Какая-то лябда, for - просто ужас. Как научиться сортировке если код не понятен ?
Ни про сложность по времени не рассказал, ни по памяти.