Пишем и подробно разбираем алгоритм Quick Sort на JavaScript | Быстрая сортировка
Вставка
- Опубліковано 19 тра 2024
- В уроке разберём алгоритм Quick Sort. Два подхода: без изменения исходного массива и с изменением, т.е. с перестановками.
🍀 Поддержать канал: www.donationalerts.com/r/webe...
☕️ Купить кофе: buy.stripe.com/5kA7sL9574SG7x...
🎨 Купить набор кистей Procreate: webelart.com/illustration.
✍️ Мой telegram channel: t.me/webelart
🏰 Английский UA-cam: @webelart_en
💁🏼♀️ Инстаграм: / webelart
🦄 LinkedIn: / webelart
Ссылки используемые в уроке:
😌 QuickSort Algorithm in JavaScript: www.guru99.com/quicksort-in-j...
😌 Видео про рекурсию: • Рекурсия и стек в Java...
😌 Видео про сложность алгоритмов: • Оценка сложности алгор...
00:00 Введение.
02:05 Описание алгоритма quick sort.
04:32 Реализуем алгоритм с созданием подмассивов.
12:10 Сложность алгоритма зависимость от опорного элемента.
14:57 Меняем опорный элемент в алгоритме.
18:10 Реализуем алгоритм quick sort с перестановками.
На канале я рассматриваю различные темы веб-разработки, на текущий момент: веб-основы, веб-анимации, веб-дизайн.
Привет Лена!
Спасибо за уроки, твои любимые подписчики смотрят, ставят лайк, комментируют!)
Привет Алексей! Спасибо, что учитесь вместе со мной! Я на вас смотрю и радуюсь! ☺️
Спасибо за подробный разбор быстрой сортировки и ждем новых видео по разбору алгоритмов!
Обязательно всем к просмотру, не только программистам 🤠. Елена tanks!)
Классно, спасибо Вам за такой труд!
Супер! Видео очень понравилось) С нетерпением жду следующее видео об алгоритмах😉🙂🎉
Желание ваше поймала, видео будут!
@@webelart 0о0 ещщёёёёёё
Спасибо за ваши старания. Больше алгоритмов ))
Елена, спасибо за алгоритмы)!
❤
Крутяк. Спасибо за актуальный видос.
Классный контент, особенно что первый способ показан где сразу всё понятно
Спасибо за урок!
Как я рада, что нашла Ваш канал 😍
❤️❤️❤️
Здорово! Подача классная. Спасибо
Спасибо! ❤
Спасибо за видео! Единственное, которое помогло мне понять этот алгоритм❤
блин ты такая крутая!!
я бы записался на твои курс по алгоритмам ))
спасибо !!
Thanks for video!
Нужно больше алгоритмов!!!
спасибо за ссылки))
😘
Спасибо- спасибо и еще много раз! Сложный вариант, даже не стала вникать) Хочу, чтобы четко в голове отложилось, а когда много инфы - каша) Почитала эту сортировку, а все равно поняла, только когда вот словами объяснили😊
Thank you
Спасибо, вспомнил молодость. :) Вообще говоря, когда работаешь на языках высокого уровня, при наличии встроенных возможностей не часто приходится реализовывать какие-то алгоритмы отдельно. Интересно было бы послушать случаи из практики, когда приходилось это делать, по каким причинам встроенные возможности не устраивали настолько, что пришлось взамен оных делать свои (если, конечно, такое было). У меня такое случалось (например, пришлось лет 11 назад писать свой парсер XML, а не использовать Microsoft-овский, что сильно сэкономило время на поддержке, когда проект внезапно "выстрелил"), но в крупной компании с разработчиками хорошего уровня (при сравнительно небольшом опыте там) подобного не встречал.
Да, тоже самое. Недавно узнала, что встроенная сортировка sort в javascript не реализует под собой quick sort, ещё все зависит от браузера. И часто это обычный insertion.
В общем сортировками уже не удивишь, но мне было интересно повторить некоторые. Bubble кстати может на собеседовании встретиться, было такое :)
@@webelart В браузерах я догадываюсь (хотя и не утверждаю точно), что уменьшение расхода памяти важнее повышения скорости сортировки: большие объёмы с бэкенда нормальный архитектор web-приложения кидать в браузер не позволит, а объём оперативной памяти на некоторых пользовательских устройствах не настолько велик, чтобы тратить его на большую сортировку; есть более полезные применения. Так что считаю, что пузырёк там вполне может быть предпочтительнее алгоритма хоть и более шустрого, но со множеством рекурсий и забитием стека.
@@webelart Задумался, к слову. Если сначала сделать один проход, сравнивая и меняя элементы с конца и начала массива (первый с последним, второй с предпоследним и так до середины), а потом пустить пузырька, сильно ли это ускорит его работу? Расход памяти, насколько я понимаю, будет чуть выше, чем в классическом пузырьке, а вот преимущества имхо могут быть.
@@webelart , а мне казалось, что sort в JS реализован сортировкой слиянием. Хотя если подумать слияние слишком затратна на небольших массивах.
воооот, совсем другое дело. сразу начало получаться. а то вот эти ваши нод джиэсы и реакты как-то не вкатили. шучу)
😂❤️🔥
Мы с вами и нод джиэсы и реакты подтянем!
Спасибо, большое. Смотрю твои видео с удовольствием. Не обращай внимание на хейтеров. Я новичок в JS поэтому все твои видео полезные. По больше видео с ООП. Очень хочется научится писать плагины, поэтому буду ждать твои видео с нетерпением).
Можете привести пример плагина, который хотите научиться писать?
@@webelart Я сейчас пишу интернет магазин и стараюсь не использовать библиотеки. Весь JS пишу сам. И вот прям по коду могу перечислить. 1. В магазине несколько меню которые открываются в виде сайдбара в меню присутствуют акордеон для того чтобы провалится в подкатегории.(например когда закрывается меню то и должен закрываться акордеон в аккардеоне подкатегория тоже закрывается и возвращается кверху ) 2. Модальные окна с оверлеем с фикс блоками где убераются падинги чтоб не скакала страница при открытии модального окна также закрывалась модалка при клики на оверлей и на мобильном устройстве чтобы можно было закрыть модалку со свайпом вниз т.е модалка при клике выезжает снизу а при свайпе вниз уезжала вниз(так чтобы сначала уезжала модалка а потом плавно убирался оверлей), также модалка убирается и при нажатии кнопки Esc и т.д. 3. Маски для телефонов такая чтоб была нормальная с валидацией изначально для +7 а также и набором из других стран. 4. Страница оформления заказа где много инпутов для ввода и адаптация странице под мобилку где чтобы тоже было удобно вводить информацию на мобилке, а также валидация уж очень там много скрытых камней ну и соответственно защита хотя бы примитивная на стороне клиента. Так же подключение какой-нибудь data для помощи в наборе улиц определенных городов. 5. Темная и светлая тема и работа с переменными в css. 6. Окно регистрации для ввода телефона и полученного кода из смс с защитой хотя бы на стороне клиента. 6. Так же много работы с local storage чтобы запоминались например клиент кликнул на сердечки в превью товара или таже самая темная и светлая тема. Конечно можно многое взять из библиотек, но сейчас такое время, что непонятно возьмут да отключать какую ни будь библиотеку для Росси и всё. Поэтому стараюсь писать все своим кодом. Извиняюсь заранее если я здесь про какие-то очевидные вещи пишу, но я новичок в этом деле, а создание интернет магазин не такая уж простая задача.
Спасибо
Почему на минуте 16:30 в цикле for, где мы поменяли значение "let i = 1" => "let i = 0", не добавили значение " - 1 " у "i < arr.length"? Если мы идем с 0 индекса массива, обычно пишут же "i < arr.length - 1"
Привет, слушай, а у тебя камера на автонастройках и автофокусе стоит? По краям прям яркость прыгает вместе с фокусом.
Мб света побольше или просто ручные настройки могли бы помочь в теории.
Ни в коем случае ни придираюсь, видео - топ. Смотрю с удовольствием.
Да, там есть автофокус. На текущем видео тоже заметила, что бывает блюрится, надо будет опять покопаться. Вообще камера у меня довольно простенькая, без каких-то наворотов.
@@webelart а, понял, принял. Ну, глянь, думаю во всем разберёшься =)
со свапом элементов в оригинальном массиве, да и как то сложнее на вид, больше по коду чтоли)
в целом первый вариант намного симпотичнее, аккуратнее и удобнее чтоли, наверное везде именно его лучше использовать
Да, мне тоже первый больше понравился :) Всё просто и понятно.
По-моему, это сортировка ещё называется сортировкой Хоара или че-то в этом роде
Да есть такое, я кстати не знала. По факту это он и написал её.
Однако нет разницы брать первый элемент в качестве опорного или центральный, конечно же, если мы не сортируем отсортированный массив. Обычно берут "случайный" элемент в качестве опорного, дабы исключить N^2 при сортировке отсортированных массивов.
Привет, а видео по Дата Стракчарс планируется?😅
:))) А что хотите про структуры данных?
@@webelart Разбор разных структур данных
и ещё интересно, а чем плох или когда использовать метод массива sort() ?
В целом для фронтенда нормально, нет обычно на фронтоне больших объемов информации. Насколько знаю под капотом sort нативный реализует простую сортировку вставками (но это зависит от браузера), она менее производительная чем quick sort. Но опять же в силу того, что на фронте не происходит манипуляция большими данными, то ок. Даже на бэке это не особо нужно. Однако если дорога каждая миллисекунда, например если большой продукт пишите, очень нагруженный. Но честно я не работала с такого уровня оптимизациями, знаю только что в Яндексе люди на фронте часто могли заморачиваться над микрооптимизациями в поиске.
@@webelart спасибо :)
@@webelart в хроме используется быстрая сортировка, в мозилле - merge sort
@@ReAgent003 Хмм, скините источник? :)
@@webelart да, конечно. На хабре пост номер 303748. Отпишитесь потом плиз, получилось ли открыть и доверяете ли вы этому источнику)
Не нужно использовать temp в swap ) [arr[i], arr[j]] = [arr[j], arr[i]] - самое лучшее для мутации массива.
Это огонь!
@@webelart А то ) Если когда то задумаете видео, где будет использоваться генерация случайной последовательности символов, то у меня есть в арсенале один магический сниппет. Там прям истинное вуду, думаю вы оцените )
@@NeverGTI Случайная последовательность любых символов? Хммм, думаю math.random на коде символа, что-нибудь такое? Правда где это юзать...
@@webelart Где юзать? Капча, например. Токенизация какая-то примитивная ) UPD Отвлекли, пропустил часть вашего ответа ) Не, кодировки напрямую тискать не придется )
Лен, ты сейчас работаешь в какой нибудь компании ?
Да, в Loveholidays www.loveholidays.com,
Хм. А есть ролики по алгоритмам, где объясняет всё девушка в бикини?
Во первых заинтересованность будет выше, а во вторых можно концентрацию тренировать :)
Ахахаа 😂😂😂 Да вы там нифига про алгоритмы не запомните.
Вроде как, самый быстрый - это алгоритм сортировки слиянием. Всегда - O(n log n)
А алгоритм быстрой сортировки:
ЛУЧШИЙ СЛУЧАЙ: - O(n log n)
СРЕДНИЙ СЛУЧАЙ: - O(n log n)
ХУДШИЙ СЛУЧАЙ: - O(n^2)
С другой стороны, в JavaScript у массивов есть метод sort, который тоже - O(n log n).
Логичный вопрос: Какой тогда смысл писать эти кастомные сортировки, которые ничем не лучше стандартной? :)
Вы знали что метод sort в javascript не quick sort реализует и часто зависит от браузера, часто это бывает обычная сортировка вставками.
Слиянием не самый быстрый. Самый быстрый как раз вот этот. И оба в худшем случае дают O(n^2). А слиянием хуже быстрой сортировки, потому что у нее константа больше, т.е. как правило в нотации О большее константа отбрасывается. Но если ее учесть, то слиянием будет хуже.
Мой встречный логичный вопрос вам, может вообще программиста нанять и нафиг это программирование? 😘
@@webelart спасибо за классный ответ) ❤ лучше, чем мое недавнее общение с ментором, который мидл, и не знает вообще об этом и расходах O(n) по памяти... Пришлось рассказывать мне ему, и он согласился, что такое есть... Даже не стал его спрашивать об этой ситуации с сортировкой.
Я просто написал о том, что вычитал в интернете) Поэтому и думаю, какой смысл изобретать велосипед)
У меня тоже есть логичный вопрос ко мне же. Постоянно задаю.
Может заниматься всё же Unity, который мне нравится, а не JS, TS и вот это вот всё, которые меня раздражают... а порой и бесят...
Но надо подстраиваться под рынок...
А сколько вам лет
32 :)
Елена, не принимай к сердцу. Я насчёт дурочка в комментариях. Ютуб для начинающих, как я. Что бл* , он тут делает вообще? Все очень умные, а ни дного знаменитого npm пакета от русского кодера не знаю. Абрамов и тот украинец. Зато все орут какой redux тупой. А где ваш state maneger или другой знаменитый в мире продукт, коли умные такие ? Задачки загадывать и я могу.
Ситник ещё есть, post css, autoprefixer. Он сейчас в Испании кажется живёт. Вообще много у нас толковых ребят. Рому Дворного ещё вспомнила, когда конфы с ним посещала, он просто космос какой-то открывал всегда. У него кстати тоже есть довольно популярные пакеты. Но я согласна, не много от русских. Надо работать и продвигать наработки в массы! ❤️
Отдельное вам спасибо за вашу поддержку и комментарий! ❤️
А вот интересно, есть ли что-нибудь подобное npm не для ноды, а, скажем, для Python (или, лучше, Python под Raspberry Pi)? Написал недавно одну либу, опубликовал у себя на сайте, но это всё же несколько не то. Думал насчёт Github, но, поскольку Microsoft делает ноги из России, имею опасения, что в один прекрасный момент пропадёт возможность заливки багфиксов, что не есть хорошо.
а первая сортировка кривоватая получилась)
Опять одно миллионное, ненужное видио из многих таких же, лучше бы рассказала куда это сувать. Где использовать луче, где применить, а то как обычно var a = 2 print(a) Ладно лайк поставлю.
За лайк спасибо! Что вас так расстраивает в миллионном? Почему не задать вопрос без лишних гневных эмоций, а просто, где это можно применить?
И видео я выпускаю в том числе по темам, которые мне хочется повторить. Чтобы был плюс плюс. Вы же мне не платите за них, чтобы я учитывала ваши желания. Подумайте об этом. А на вопросы я обычно стараюсь отвечать.
@@webelart Ясно, продажная, лайк убираю)) Назови свою цену.
@@webelart А за что вам платить? Сможешь сделать карту 10 на 10, с рандомной рекой в 2 тайла, которая будет течь с одного края в другой? (И тут кто то сдулся))
@@logius84 Если нужно будет, сделаю, но стоить будет дорого. Давайте вернёмся к текущей теме, вы считаете, что труд не должен оплачиваться? А на работе вы деньги только за такие карты получаете?