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