Быстрая сортировка в python. Quick sort in Python. Recursive sorting algorithms
HTML-код
- Опубликовано: 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
В данном группе можете найти информацию о новых видео и задать вопросы
Отличный преподаватель. Алгоритмы - в плейлист.
Спасибо, Егор, по моему самое адекватное объяснение. И слушать приятно)).
Спасибо, наконец-то разобрался с рекурсией
Спасибо! Наконец-то понял. Отдельная благодарность за демонстрацию работы с отладчиком.
Выглядит как магия!
_Большое спасибо за урок!_ Этот понятнее, чем предыдущий)
Огромное спасибо за алгоритмы.
Лучшее объяснение что нашел на ютубе. Благодарю
Уф, целых три цикла перебора вместо одного, супер эффективно:D
красавчик. Объяснил все на понятном языке. Недавно начал читать книгу:"грокаем алгоритмы",вот и не понял алгоритм быстрой сортировки,а ты все прям разжевал как надо. Подписочка оформлена!
А в целом очень хорошо и понятно объясняете
Спасибо за видео. Я проверил два способа:
1) с использованием метода filter
2) генератор списка через [el for el in arr if el (, ==) pivot]
Вывод: второй метод быстрее, так как не идет вызов функций (а такая операция в питоне происходит не слишком быстро). Возможно, в другом языке ситуация будет иная.
Спасибо!
ясно и понятно...
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)
или получается одно и то же, ведь мы каждый элемент в худшем случае проверяем дважды?
Вы создаете на каждой итерации рекурсии новые списки- при больших начальных списках память уйдет очень быстро. Изначальный алгоритм быстрой сортировки - эта работа с указателями.
он изначально сказал "один из способов быстрой сортировки", что это подразумевает под собой?!?!? способ на то и способ, что подходит для определённых ситуаций, когда список маленький - пожалуйста, пользуйся! большой?! ищи идею лучше!
@@trahar отчасти согласен с вашим рассуждением. Отчасти нет.
1. По поводу лучшего способа - лучший способ на сегодняшний момент - это как раз пользоваться встроенными средствами языка.
2. Здесь мы разбираем классические алгоритмы. Соответственно было бы не плохо указать плюсы и минусы этих алгоритмов. Плюс Quick search как раз таки в том, что он должен работать с одним списком как объект, не создавая новых, и не захламляя память. Автор очень хорошо и понятно объяснил суть работы алгоритма на примере создания списков... Но наверное стоило бы потом и перейти на классическую его реализацию... С объяснением и разбором.
@@arxxximed это да! так-то и нужно
+ каждый раз список перебирается по 3 раза
по итогу сортировка замедляется в 3 раза
теперь это медленная сортировка = )
Спасибо
Яке це швидке сортування якщо ви створюєте нові масиви. Тобто відміність швидкого сортуввння від сортування злиттям зникає. (їх відміність в просторовій суладності)
В "Грохаем алгоритмы" есть фраза - "Если вы всегда
будете выбирать опорным элементом случайный элемент в массиве, бы
страя сортировка в среднем завершится за время О(п log п). " - при этом результирующий массив отличается по количеству элементов от искомого (по вашей программе)((( Как это исправить??
Вы в самом начале ролика сказали что можно брать любой элемент. Это явно ошибка потому что при увеличении размеров списка и например если мы берем первый элемент - скорость вашей работы будет заведомо меньше чем при серединном элементе. Это можно явно заметить при быстрой сортировке с разбиением дейкстры. Если в этом случае вы берете первый элемент - у вас идет сильный упадок скорости. Этот момент нужно подметить и учесть что каждый элемент должен быть - element = array[len(array) // 2] - вот в таком случае на каждой итерации будет решать за nlogn
Учтите это после просмотра!
А выбор рандомного опорного элемента тоже будет занимать nlogn?
Такой вопрос, несколько глупый может быть, но для меня пока актуальный. Почему алгоритм является более быстрым, если в обычной сортировке, методом перебора всех элементов и перестановки позиций, так же проверяется каждый элемент, но в этом методе ещё больше действий кроме перебора элементов? И это ещё не говоря о вложенности, которая при огромных массивах вообще может нехило занять память.
из-за рекурсии думаю
количество этих самых переборов другое.
попробуй руками отсортировать список пузырьком и квиксортом, считая количество сравнений и перестановок.
что бы разница была видна, список побольше взять, 7+ элементов
Эх, кто бы ещё объяснил, зачем знать алгоритмы сортировки разработчику на 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)
так был же пример, а если ты выбрал в качестве ключевого элемента семерку, а у тебя в списке 30 семерок?
Остальные семерки в какую сторону пойдут в right или left?
Al Zhuch делаешь тогда меньше либо равно в left, либо наоборот в right
@@obe1313 И можешь столкнуться с бесконечным циклом
)))))) Ты попробуй написать эту прогу
@@arxxximed, каким образом там бесконечный цикл появляется?
программирование не твое, иди в начальники)
Команда на выход приводит к ошибке.
Немного переделал:
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 - просто ужас. Как научиться сортировке если код не понятен ?
Ни про сложность по времени не рассказал, ни по памяти.