Пишем и подробно разбираем алгоритм 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

  • @yankov2206
    @yankov2206 Жыл бұрын

    Привет Лена! Спасибо за уроки, твои любимые подписчики смотрят, ставят лайк, комментируют!)

  • @webelart

    @webelart

    Жыл бұрын

    Привет Алексей! Спасибо, что учитесь вместе со мной! Я на вас смотрю и радуюсь! ☺️

  • @slava_po
    @slava_po Жыл бұрын

    Обязательно всем к просмотру, не только программистам 🤠. Елена tanks!)

  • @mukhammadakilov2828
    @mukhammadakilov2828 Жыл бұрын

    Классно, спасибо Вам за такой труд!

  • @volodymyrnerovnia5143
    @volodymyrnerovnia5143 Жыл бұрын

    Спасибо за подробный разбор быстрой сортировки и ждем новых видео по разбору алгоритмов!

  • @the-tata
    @the-tata Жыл бұрын

    Крутяк. Спасибо за актуальный видос.

  • @gleb6843
    @gleb6843 Жыл бұрын

    Спасибо за ваши старания. Больше алгоритмов ))

  • @jamesmay5088
    @jamesmay5088 Жыл бұрын

    Супер! Видео очень понравилось) С нетерпением жду следующее видео об алгоритмах😉🙂🎉

  • @webelart

    @webelart

    Жыл бұрын

    Желание ваше поймала, видео будут!

  • @mikaelgevorgyan4521

    @mikaelgevorgyan4521

    Жыл бұрын

    @@webelart 0о0 ещщёёёёёё

  • @k-ivan
    @k-ivan Жыл бұрын

    Елена, спасибо за алгоритмы)!

  • @webelart

    @webelart

    Жыл бұрын

  • @rostyslavkinash5232
    @rostyslavkinash52324 ай бұрын

    Спасибо за урок!

  • @verccety1
    @verccety1 Жыл бұрын

    Классный контент, особенно что первый способ показан где сразу всё понятно

  • @user-jq3sz4hg6k
    @user-jq3sz4hg6k5 ай бұрын

    Здорово! Подача классная. Спасибо

  • @webelart

    @webelart

    5 ай бұрын

    Спасибо! ❤

  • @user-yj8tf7xb6g
    @user-yj8tf7xb6g7 ай бұрын

    Как я рада, что нашла Ваш канал 😍

  • @webelart

    @webelart

    5 ай бұрын

    ❤️❤️❤️

  • @Svetavo_o
    @Svetavo_o Жыл бұрын

    Спасибо за видео! Единственное, которое помогло мне понять этот алгоритм❤

  • @VeloGitaryst
    @VeloGitaryst Жыл бұрын

    Thanks for video!

  • @user-gg7cg7gz9o
    @user-gg7cg7gz9o10 ай бұрын

    блин ты такая крутая!! я бы записался на твои курс по алгоритмам )) спасибо !!

  • @user-ij8sn3sr6z
    @user-ij8sn3sr6z Жыл бұрын

    спасибо за ссылки))

  • @webelart

    @webelart

    Жыл бұрын

    😘

  • @nagibbator4449
    @nagibbator4449 Жыл бұрын

    Thank you

  • @jonmace3522
    @jonmace3522 Жыл бұрын

    Нужно больше алгоритмов!!!

  • @user-ym7gg5ki6l
    @user-ym7gg5ki6l Жыл бұрын

    Спасибо

  • @user-jt9yd6vr8b
    @user-jt9yd6vr8b Жыл бұрын

    Спасибо, вспомнил молодость. :) Вообще говоря, когда работаешь на языках высокого уровня, при наличии встроенных возможностей не часто приходится реализовывать какие-то алгоритмы отдельно. Интересно было бы послушать случаи из практики, когда приходилось это делать, по каким причинам встроенные возможности не устраивали настолько, что пришлось взамен оных делать свои (если, конечно, такое было). У меня такое случалось (например, пришлось лет 11 назад писать свой парсер XML, а не использовать Microsoft-овский, что сильно сэкономило время на поддержке, когда проект внезапно "выстрелил"), но в крупной компании с разработчиками хорошего уровня (при сравнительно небольшом опыте там) подобного не встречал.

  • @webelart

    @webelart

    Жыл бұрын

    Да, тоже самое. Недавно узнала, что встроенная сортировка sort в javascript не реализует под собой quick sort, ещё все зависит от браузера. И часто это обычный insertion. В общем сортировками уже не удивишь, но мне было интересно повторить некоторые. Bubble кстати может на собеседовании встретиться, было такое :)

  • @user-jt9yd6vr8b

    @user-jt9yd6vr8b

    Жыл бұрын

    @@webelart В браузерах я догадываюсь (хотя и не утверждаю точно), что уменьшение расхода памяти важнее повышения скорости сортировки: большие объёмы с бэкенда нормальный архитектор web-приложения кидать в браузер не позволит, а объём оперативной памяти на некоторых пользовательских устройствах не настолько велик, чтобы тратить его на большую сортировку; есть более полезные применения. Так что считаю, что пузырёк там вполне может быть предпочтительнее алгоритма хоть и более шустрого, но со множеством рекурсий и забитием стека.

  • @user-jt9yd6vr8b

    @user-jt9yd6vr8b

    Жыл бұрын

    @@webelart Задумался, к слову. Если сначала сделать один проход, сравнивая и меняя элементы с конца и начала массива (первый с последним, второй с предпоследним и так до середины), а потом пустить пузырька, сильно ли это ускорит его работу? Расход памяти, насколько я понимаю, будет чуть выше, чем в классическом пузырьке, а вот преимущества имхо могут быть.

  • @user-do3zm3vp2f

    @user-do3zm3vp2f

    11 ай бұрын

    @@webelart , а мне казалось, что sort в JS реализован сортировкой слиянием. Хотя если подумать слияние слишком затратна на небольших массивах.

  • @user-nm8gh5wp3s
    @user-nm8gh5wp3s Жыл бұрын

    Спасибо, большое. Смотрю твои видео с удовольствием. Не обращай внимание на хейтеров. Я новичок в JS поэтому все твои видео полезные. По больше видео с ООП. Очень хочется научится писать плагины, поэтому буду ждать твои видео с нетерпением).

  • @webelart

    @webelart

    Жыл бұрын

    Можете привести пример плагина, который хотите научиться писать?

  • @user-nm8gh5wp3s

    @user-nm8gh5wp3s

    Жыл бұрын

    @@webelart Я сейчас пишу интернет магазин и стараюсь не использовать библиотеки. Весь JS пишу сам. И вот прям по коду могу перечислить. 1. В магазине несколько меню которые открываются в виде сайдбара в меню присутствуют акордеон для того чтобы провалится в подкатегории.(например когда закрывается меню то и должен закрываться акордеон в аккардеоне подкатегория тоже закрывается и возвращается кверху ) 2. Модальные окна с оверлеем с фикс блоками где убераются падинги чтоб не скакала страница при открытии модального окна также закрывалась модалка при клики на оверлей и на мобильном устройстве чтобы можно было закрыть модалку со свайпом вниз т.е модалка при клике выезжает снизу а при свайпе вниз уезжала вниз(так чтобы сначала уезжала модалка а потом плавно убирался оверлей), также модалка убирается и при нажатии кнопки Esc и т.д. 3. Маски для телефонов такая чтоб была нормальная с валидацией изначально для +7 а также и набором из других стран. 4. Страница оформления заказа где много инпутов для ввода и адаптация странице под мобилку где чтобы тоже было удобно вводить информацию на мобилке, а также валидация уж очень там много скрытых камней ну и соответственно защита хотя бы примитивная на стороне клиента. Так же подключение какой-нибудь data для помощи в наборе улиц определенных городов. 5. Темная и светлая тема и работа с переменными в css. 6. Окно регистрации для ввода телефона и полученного кода из смс с защитой хотя бы на стороне клиента. 6. Так же много работы с local storage чтобы запоминались например клиент кликнул на сердечки в превью товара или таже самая темная и светлая тема. Конечно можно многое взять из библиотек, но сейчас такое время, что непонятно возьмут да отключать какую ни будь библиотеку для Росси и всё. Поэтому стараюсь писать все своим кодом. Извиняюсь заранее если я здесь про какие-то очевидные вещи пишу, но я новичок в этом деле, а создание интернет магазин не такая уж простая задача.

  • @99k27
    @99k27 Жыл бұрын

    воооот, совсем другое дело. сразу начало получаться. а то вот эти ваши нод джиэсы и реакты как-то не вкатили. шучу)

  • @webelart

    @webelart

    Жыл бұрын

    😂❤️‍🔥

  • @webelart

    @webelart

    Жыл бұрын

    Мы с вами и нод джиэсы и реакты подтянем!

  • @user-tk7qv9rv2c
    @user-tk7qv9rv2c Жыл бұрын

    Спасибо- спасибо и еще много раз! Сложный вариант, даже не стала вникать) Хочу, чтобы четко в голове отложилось, а когда много инфы - каша) Почитала эту сортировку, а все равно поняла, только когда вот словами объяснили😊

  • @shanksredhaired1632
    @shanksredhaired1632Ай бұрын

    Почему на минуте 16:30 в цикле for, где мы поменяли значение "let i = 1" => "let i = 0", не добавили значение " - 1 " у "i < arr.length"? Если мы идем с 0 индекса массива, обычно пишут же "i < arr.length - 1"

  • @konstantinov_it
    @konstantinov_it7 ай бұрын

    Однако нет разницы брать первый элемент в качестве опорного или центральный, конечно же, если мы не сортируем отсортированный массив. Обычно берут "случайный" элемент в качестве опорного, дабы исключить N^2 при сортировке отсортированных массивов.

  • @Di-yes
    @Di-yes Жыл бұрын

    Привет, слушай, а у тебя камера на автонастройках и автофокусе стоит? По краям прям яркость прыгает вместе с фокусом. Мб света побольше или просто ручные настройки могли бы помочь в теории. Ни в коем случае ни придираюсь, видео - топ. Смотрю с удовольствием.

  • @webelart

    @webelart

    Жыл бұрын

    Да, там есть автофокус. На текущем видео тоже заметила, что бывает блюрится, надо будет опять покопаться. Вообще камера у меня довольно простенькая, без каких-то наворотов.

  • @Di-yes

    @Di-yes

    Жыл бұрын

    @@webelart а, понял, принял. Ну, глянь, думаю во всем разберёшься =)

  • @soldat675
    @soldat675 Жыл бұрын

    со свапом элементов в оригинальном массиве, да и как то сложнее на вид, больше по коду чтоли) в целом первый вариант намного симпотичнее, аккуратнее и удобнее чтоли, наверное везде именно его лучше использовать

  • @webelart

    @webelart

    Жыл бұрын

    Да, мне тоже первый больше понравился :) Всё просто и понятно.

  • @user-mh9pe4zp6l
    @user-mh9pe4zp6l Жыл бұрын

    По-моему, это сортировка ещё называется сортировкой Хоара или че-то в этом роде

  • @webelart

    @webelart

    Жыл бұрын

    Да есть такое, я кстати не знала. По факту это он и написал её.

  • @bolovy6093
    @bolovy6093 Жыл бұрын

    Привет, а видео по Дата Стракчарс планируется?😅

  • @webelart

    @webelart

    Жыл бұрын

    :))) А что хотите про структуры данных?

  • @bolovy6093

    @bolovy6093

    Жыл бұрын

    @@webelart Разбор разных структур данных

  • @soldat675
    @soldat675 Жыл бұрын

    и ещё интересно, а чем плох или когда использовать метод массива sort() ?

  • @webelart

    @webelart

    Жыл бұрын

    В целом для фронтенда нормально, нет обычно на фронтоне больших объемов информации. Насколько знаю под капотом sort нативный реализует простую сортировку вставками (но это зависит от браузера), она менее производительная чем quick sort. Но опять же в силу того, что на фронте не происходит манипуляция большими данными, то ок. Даже на бэке это не особо нужно. Однако если дорога каждая миллисекунда, например если большой продукт пишите, очень нагруженный. Но честно я не работала с такого уровня оптимизациями, знаю только что в Яндексе люди на фронте часто могли заморачиваться над микрооптимизациями в поиске.

  • @soldat675

    @soldat675

    Жыл бұрын

    @@webelart спасибо :)

  • @ReAgent003

    @ReAgent003

    Жыл бұрын

    @@webelart в хроме используется быстрая сортировка, в мозилле - merge sort

  • @webelart

    @webelart

    Жыл бұрын

    @@ReAgent003 Хмм, скините источник? :)

  • @ReAgent003

    @ReAgent003

    Жыл бұрын

    @@webelart да, конечно. На хабре пост номер 303748. Отпишитесь потом плиз, получилось ли открыть и доверяете ли вы этому источнику)

  • @NeverGTI
    @NeverGTI Жыл бұрын

    Не нужно использовать temp в swap ) [arr[i], arr[j]] = [arr[j], arr[i]] - самое лучшее для мутации массива.

  • @webelart

    @webelart

    Жыл бұрын

    Это огонь!

  • @NeverGTI

    @NeverGTI

    Жыл бұрын

    @@webelart А то ) Если когда то задумаете видео, где будет использоваться генерация случайной последовательности символов, то у меня есть в арсенале один магический сниппет. Там прям истинное вуду, думаю вы оцените )

  • @webelart

    @webelart

    Жыл бұрын

    @@NeverGTI Случайная последовательность любых символов? Хммм, думаю math.random на коде символа, что-нибудь такое? Правда где это юзать...

  • @NeverGTI

    @NeverGTI

    Жыл бұрын

    @@webelart Где юзать? Капча, например. Токенизация какая-то примитивная ) UPD Отвлекли, пропустил часть вашего ответа ) Не, кодировки напрямую тискать не придется )

  • @NeoJohnSmit
    @NeoJohnSmit Жыл бұрын

    Лен, ты сейчас работаешь в какой нибудь компании ?

  • @webelart

    @webelart

    Жыл бұрын

    Да, в Loveholidays www.loveholidays.com,

  • @andrewbondaryuk
    @andrewbondaryuk Жыл бұрын

    Хм. А есть ролики по алгоритмам, где объясняет всё девушка в бикини? Во первых заинтересованность будет выше, а во вторых можно концентрацию тренировать :)

  • @webelart

    @webelart

    Жыл бұрын

    Ахахаа 😂😂😂 Да вы там нифига про алгоритмы не запомните.

  • @user-hx5yw6nn2x
    @user-hx5yw6nn2x Жыл бұрын

    А сколько вам лет

  • @webelart

    @webelart

    Жыл бұрын

    32 :)

  • @codeforgames
    @codeforgames Жыл бұрын

    Вроде как, самый быстрый - это алгоритм сортировки слиянием. Всегда - O(n log n) А алгоритм быстрой сортировки: ЛУЧШИЙ СЛУЧАЙ: - O(n log n) СРЕДНИЙ СЛУЧАЙ: - O(n log n) ХУДШИЙ СЛУЧАЙ: - O(n^2) С другой стороны, в JavaScript у массивов есть метод sort, который тоже - O(n log n). Логичный вопрос: Какой тогда смысл писать эти кастомные сортировки, которые ничем не лучше стандартной? :)

  • @webelart

    @webelart

    Жыл бұрын

    Вы знали что метод sort в javascript не quick sort реализует и часто зависит от браузера, часто это бывает обычная сортировка вставками. Слиянием не самый быстрый. Самый быстрый как раз вот этот. И оба в худшем случае дают O(n^2). А слиянием хуже быстрой сортировки, потому что у нее константа больше, т.е. как правило в нотации О большее константа отбрасывается. Но если ее учесть, то слиянием будет хуже. Мой встречный логичный вопрос вам, может вообще программиста нанять и нафиг это программирование? 😘

  • @codeforgames

    @codeforgames

    Жыл бұрын

    @@webelart спасибо за классный ответ) ❤ лучше, чем мое недавнее общение с ментором, который мидл, и не знает вообще об этом и расходах O(n) по памяти... Пришлось рассказывать мне ему, и он согласился, что такое есть... Даже не стал его спрашивать об этой ситуации с сортировкой. Я просто написал о том, что вычитал в интернете) Поэтому и думаю, какой смысл изобретать велосипед) У меня тоже есть логичный вопрос ко мне же. Постоянно задаю. Может заниматься всё же Unity, который мне нравится, а не JS, TS и вот это вот всё, которые меня раздражают... а порой и бесят... Но надо подстраиваться под рынок...

  • @fedordostoevskiy4209
    @fedordostoevskiy4209 Жыл бұрын

    Елена, не принимай к сердцу. Я насчёт дурочка в комментариях. Ютуб для начинающих, как я. Что бл* , он тут делает вообще? Все очень умные, а ни дного знаменитого npm пакета от русского кодера не знаю. Абрамов и тот украинец. Зато все орут какой redux тупой. А где ваш state maneger или другой знаменитый в мире продукт, коли умные такие ? Задачки загадывать и я могу.

  • @webelart

    @webelart

    Жыл бұрын

    Ситник ещё есть, post css, autoprefixer. Он сейчас в Испании кажется живёт. Вообще много у нас толковых ребят. Рому Дворного ещё вспомнила, когда конфы с ним посещала, он просто космос какой-то открывал всегда. У него кстати тоже есть довольно популярные пакеты. Но я согласна, не много от русских. Надо работать и продвигать наработки в массы! ❤️ Отдельное вам спасибо за вашу поддержку и комментарий! ❤️

  • @user-jt9yd6vr8b

    @user-jt9yd6vr8b

    Жыл бұрын

    А вот интересно, есть ли что-нибудь подобное npm не для ноды, а, скажем, для Python (или, лучше, Python под Raspberry Pi)? Написал недавно одну либу, опубликовал у себя на сайте, но это всё же несколько не то. Думал насчёт Github, но, поскольку Microsoft делает ноги из России, имею опасения, что в один прекрасный момент пропадёт возможность заливки багфиксов, что не есть хорошо.

  • @Fo-Lem
    @Fo-Lem11 ай бұрын

    а первая сортировка кривоватая получилась)

  • @logius84
    @logius84 Жыл бұрын

    Опять одно миллионное, ненужное видио из многих таких же, лучше бы рассказала куда это сувать. Где использовать луче, где применить, а то как обычно var a = 2 print(a) Ладно лайк поставлю.

  • @webelart

    @webelart

    Жыл бұрын

    За лайк спасибо! Что вас так расстраивает в миллионном? Почему не задать вопрос без лишних гневных эмоций, а просто, где это можно применить?

  • @webelart

    @webelart

    Жыл бұрын

    И видео я выпускаю в том числе по темам, которые мне хочется повторить. Чтобы был плюс плюс. Вы же мне не платите за них, чтобы я учитывала ваши желания. Подумайте об этом. А на вопросы я обычно стараюсь отвечать.

  • @logius84

    @logius84

    Жыл бұрын

    @@webelart Ясно, продажная, лайк убираю)) Назови свою цену.

  • @logius84

    @logius84

    Жыл бұрын

    @@webelart А за что вам платить? Сможешь сделать карту 10 на 10, с рандомной рекой в 2 тайла, которая будет течь с одного края в другой? (И тут кто то сдулся))

  • @webelart

    @webelart

    Жыл бұрын

    @@logius84 Если нужно будет, сделаю, но стоить будет дорого. Давайте вернёмся к текущей теме, вы считаете, что труд не должен оплачиваться? А на работе вы деньги только за такие карты получаете?

Келесі