Быстрая сортировка за 4 минуты. Алгоритмы на JavaScript
Вставка
- Опубліковано 8 жов 2024
- В этом видео мы разберём популярный на собеседованиях алгоритм быстрой сортировки. Интересный факт, алгоритм quick sort используется под капотом в движке v8 на массивах длины 10 и более (ранее было от 22).
Мой телеграм канал: t.me/konstanti...
Потренируйтесь в реализации quick sort на leetcode:
leetcode.com/p...
Пишите в комментариях, если хотите, чтобы я разобрал реализацию алгоритмов пирамидальной сортировки, сортировки вставками, пузырьковой или любой другой.
Классно объясняешь. Ждем больше видео про Алгоритмы
Теория большого взрыва закончился а я по-прежнему слушаю Шелдона Купера но он молодец даже русский выучил с кубанским акцентом красавчик)
очень классно объяснил, продолжай не останавливайся!
Ждём следующих видосов!
Я ни чего не знаю про алгоритмы, но зачем два раза использовать slice и filter? Тогда уж лучше пройтись for и записать нужные значения в переменные, в два раза производительнее
Привет! Согласен, использовать цикл for будет оптимальнее. Так или иначе, это никак не влияет на асимптотическую сложность и основная идея алгоритма остаётся прежней. В видео хотел донести основную идею алгоритма, а так мне показалось весьма лаконично. Благо во всех современных языках есть уже нативные реализации сортировки
вы сами ответили на свой вопрос, вы не знаете алгоритмы, поэтому не понимаете, что для простого примера, как в видео, быстрее будет использовать цикл, но для более сложных цикл будет медленнее
Спасибо тебе огромное! Я настолько простого и понятного объяснения не видел. Ожидаю еще видосов про алго))
А почему везде предлагается использовать рандомный элемент в качестве опорного, когда можно брать серединный?
Предполагаю, обоснование этому вероятностно-статистическое. При выборе любого постоянного номера элемента в массиве существует такой массив, сложность сортировки которого будет O(n^2), как в примере с выбором 1-го элемента. Подобрал массив [4,2,1,3,5], где при выборе центрального (левого) элемента мы получим O(n^2). Выбор же случайного элемента избавляет нас от такого сценария. Хотя не исключено, что возможен сценарий худшего случая, но в диапазоне M повторений его вероятность сильно меньше. В целом, это моё предположение, но я думаю, что оно не далеко от истины.
ПАДЕНИЕ ОЛИМПА
⚡
А смысл в этом всем если ты фильтр используешь? Тогда уже можно просто сорт использовать…
Смысл в том, чтобы продемонстрировать алгоритм. Благо он же реализован под капотом в методе sort для длинных массивов
Сергей, у Вас упало!
Поднял!
Щас бы быструю сортировку писать с фильтром и прочими мптодами. Кстати у того что ьы написал не n log n сложность почитай свой код
Привет! А почему бы и нет? Думаю, оптимальнее было бы сразу написать на C. Благо в современных языках уже есть низкоуровневая реализация сортировки. В частности в JS это метод sort, который применяет быструю сортировку на массивах длины > 10. В видео же хотел показать основной принцип работы алгоритма. А по поводу сложности, всё же O(N*logN) (в худшем O(N^2), о чем говорится в видео)
Отличное видео! Только гэканье режет слух