Спасибо за видео. Я проверил два способа: 1) с использованием метода filter 2) генератор списка через [el for el in arr if el (, ==) pivot] Вывод: второй метод быстрее, так как не идет вызов функций (а такая операция в питоне происходит не слишком быстро). Возможно, в другом языке ситуация будет иная.
красавчик. Объяснил все на понятном языке. Недавно начал читать книгу:"грокаем алгоритмы",вот и не понял алгоритм быстрой сортировки,а ты все прям разжевал как надо. Подписочка оформлена!
Вы создаете на каждой итерации рекурсии новые списки- при больших начальных списках память уйдет очень быстро. Изначальный алгоритм быстрой сортировки - эта работа с указателями.
он изначально сказал "один из способов быстрой сортировки", что это подразумевает под собой?!?!? способ на то и способ, что подходит для определённых ситуаций, когда список маленький - пожалуйста, пользуйся! большой?! ищи идею лучше!
@@trahar отчасти согласен с вашим рассуждением. Отчасти нет. 1. По поводу лучшего способа - лучший способ на сегодняшний момент - это как раз пользоваться встроенными средствами языка. 2. Здесь мы разбираем классические алгоритмы. Соответственно было бы не плохо указать плюсы и минусы этих алгоритмов. Плюс Quick search как раз таки в том, что он должен работать с одним списком как объект, не создавая новых, и не захламляя память. Автор очень хорошо и понятно объяснил суть работы алгоритма на примере создания списков... Но наверное стоило бы потом и перейти на классическую его реализацию... С объяснением и разбором.
скажите, товарищи, а такого рода многократные пробежки не тратят ли больше памяти и времени? я понимаю, это генераторы, однако в каждом следующем генераторе мы проверяем каждый элемент повторно! не эффективнее ли запустить один цикл и в нём проверять величину переменной? for i in lst: if i < base: less.append(i) elif i > base: bigger.append(i) else: centre.append(i) или получается одно и то же, ведь мы каждый элемент в худшем случае проверяем дважды?
В "Грохаем алгоритмы" есть фраза - "Если вы всегда будете выбирать опорным элементом случайный элемент в массиве, бы страя сортировка в среднем завершится за время О(п log п). " - при этом результирующий массив отличается по количеству элементов от искомого (по вашей программе)((( Как это исправить??
Вы в самом начале ролика сказали что можно брать любой элемент. Это явно ошибка потому что при увеличении размеров списка и например если мы берем первый элемент - скорость вашей работы будет заведомо меньше чем при серединном элементе. Это можно явно заметить при быстрой сортировке с разбиением дейкстры. Если в этом случае вы берете первый элемент - у вас идет сильный упадок скорости. Этот момент нужно подметить и учесть что каждый элемент должен быть - element = array[len(array) // 2] - вот в таком случае на каждой итерации будет решать за nlogn Учтите это после просмотра!
Такой вопрос, несколько глупый может быть, но для меня пока актуальный. Почему алгоритм является более быстрым, если в обычной сортировке, методом перебора всех элементов и перестановки позиций, так же проверяется каждый элемент, но в этом методе ещё больше действий кроме перебора элементов? И это ещё не говоря о вложенности, которая при огромных массивах вообще может нехило занять память.
количество этих самых переборов другое. попробуй руками отсортировать список пузырьком и квиксортом, считая количество сравнений и перестановок. что бы разница была видна, список побольше взять, 7+ элементов
Нет универсального алгоритма, и не смотря на то, что в питоне умный сортировщик и он использует несколько алгоритмов, возможна ситуация когда тебе для оптимального решения текущей задачи нужен конкретный алгоритм сортировки, для этого нужно знать алгоритмы сортировки, их слабые и сильные места. А тут задачу изменили нужный алгоритм из гугла не работает, его нужно чуть изменить под специфику задачи, скажем сделать не устойчивым и ещё что-то там. Теперь тебе нужно знать не только что существует такой алгоритм, но и как он работает и что нужно изменить в нём для решения проблемы. Алгоримы это история про эффективность, понимая как их делают такими быстрыми можно в принципе писать более чистый код, который легче читать ещё он будет быстрее и в нём не будет лишних условий\сомнительных решений. И даже решая другую задачу принцип решения алгоритмов может быть полезен: придумай наивное решение, разбей задачу, найди бутылочное горлышко, сделай рефакторинг -> повторяй до оптимального результата.
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
зачем 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?
Яке це швидке сортування якщо ви створюєте нові масиви. Тобто відміність швидкого сортуввння від сортування злиттям зникає. (їх відміність в просторовій суладності)
У меня вопрос возник, а почему все эти супер пупер алгоритмы изначально не встроить в языке программирования в качестве встроенных функций ? Почему нужно свои костыли делать ?
Ахахах, программист нашелся... Задача не отсортировать что-то а понять принцип работы данного алгоритма. Как минимум по твоему комментарию можно прийти к выводу что программирование это не твоё. Не знаю, займись чем-нибудь другим.
Отличный преподаватель. Алгоритмы - в плейлист.
Спасибо за видео. Я проверил два способа:
1) с использованием метода filter
2) генератор списка через [el for el in arr if el (, ==) pivot]
Вывод: второй метод быстрее, так как не идет вызов функций (а такая операция в питоне происходит не слишком быстро). Возможно, в другом языке ситуация будет иная.
Спасибо, Егор, по моему самое адекватное объяснение. И слушать приятно)).
красавчик. Объяснил все на понятном языке. Недавно начал читать книгу:"грокаем алгоритмы",вот и не понял алгоритм быстрой сортировки,а ты все прям разжевал как надо. Подписочка оформлена!
Спасибо! Наконец-то понял. Отдельная благодарность за демонстрацию работы с отладчиком.
Спасибо, наконец-то разобрался с рекурсией
Выглядит как магия!
Я использую combosort годами, он прекрасно вписьівается в целочисленную математику, и не изпользует много оперативки и стека.
Лучшее объяснение что нашел на ютубе. Благодарю
_Большое спасибо за урок!_ Этот понятнее, чем предыдущий)
Уф, целых три цикла перебора вместо одного, супер эффективно:D
Огромное спасибо за алгоритмы.
Вы создаете на каждой итерации рекурсии новые списки- при больших начальных списках память уйдет очень быстро. Изначальный алгоритм быстрой сортировки - эта работа с указателями.
он изначально сказал "один из способов быстрой сортировки", что это подразумевает под собой?!?!? способ на то и способ, что подходит для определённых ситуаций, когда список маленький - пожалуйста, пользуйся! большой?! ищи идею лучше!
@@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)
или получается одно и то же, ведь мы каждый элемент в худшем случае проверяем дважды?
Спасибо!
elem = s[len(s)//2] вот так должно быть. А иначе при выборе элементов > 2 ошибку выбивает
А в целом очень хорошо и понятно объясняете
Ты хорош !)
есть разница в скорости выполнения алгоритма исходя из того какой элемент брать за базовый?
ясно и понятно...
Спасибо
В "Грохаем алгоритмы" есть фраза - "Если вы всегда
будете выбирать опорным элементом случайный элемент в массиве, бы
страя сортировка в среднем завершится за время О(п log п). " - при этом результирующий массив отличается по количеству элементов от искомого (по вашей программе)((( Как это исправить??
Что это за курс на степике?
Вы в самом начале ролика сказали что можно брать любой элемент. Это явно ошибка потому что при увеличении размеров списка и например если мы берем первый элемент - скорость вашей работы будет заведомо меньше чем при серединном элементе. Это можно явно заметить при быстрой сортировке с разбиением дейкстры. Если в этом случае вы берете первый элемент - у вас идет сильный упадок скорости. Этот момент нужно подметить и учесть что каждый элемент должен быть - element = array[len(array) // 2] - вот в таком случае на каждой итерации будет решать за nlogn
Учтите это после просмотра!
А выбор рандомного опорного элемента тоже будет занимать nlogn?
Через фильтр большой список становится далеко не быстрым для сортировки
Такой вопрос, несколько глупый может быть, но для меня пока актуальный. Почему алгоритм является более быстрым, если в обычной сортировке, методом перебора всех элементов и перестановки позиций, так же проверяется каждый элемент, но в этом методе ещё больше действий кроме перебора элементов? И это ещё не говоря о вложенности, которая при огромных массивах вообще может нехило занять память.
из-за рекурсии думаю
количество этих самых переборов другое.
попробуй руками отсортировать список пузырьком и квиксортом, считая количество сравнений и перестановок.
что бы разница была видна, список побольше взять, 7+ элементов
Эх, кто бы ещё объяснил, зачем знать алгоритмы сортировки разработчику на 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
сортировка летит на массиве из равных элементов
зачем 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, каким образом там бесконечный цикл появляется?
программирование не твое, иди в начальники)
Яке це швидке сортування якщо ви створюєте нові масиви. Тобто відміність швидкого сортуввння від сортування злиттям зникає. (їх відміність в просторовій суладності)
У меня вопрос возник, а почему все эти супер пупер алгоритмы изначально не встроить в языке программирования в качестве встроенных функций ? Почему нужно свои костыли делать ?
так они есть. алгоритмы надо изучать не для того что их самому писать, а что понимать как работает то что уже написано
Быстрая сортировка ---> sort(....)
можешь отписаться от канала и больше не смотреть никаких материалов на тему сортировки, раз такой умник
Ахахах, программист нашелся... Задача не отсортировать что-то а понять принцип работы данного алгоритма. Как минимум по твоему комментарию можно прийти к выводу что программирование это не твоё. Не знаю, займись чем-нибудь другим.
Объяснение хорошее, но код кошмар для новичков. Какая-то лябда, for - просто ужас. Как научиться сортировке если код не понятен ?
*ваавав*
Ни про сложность по времени не рассказал, ни по памяти.
спасибо