C# QuickSort Быстрая сортировка

Подписаться 22 тыс.

Просмотров 29 тыс.

50% 1

В данном ролике мы поговорим об одном из самых популярных алгоритмов сортировки массивов - быстрая сортировка QuickSort (или быстрая сортировка Хоара). Рассмотрим концепцию алгоритма и посмотрим на отличную визуализацию, где всё станет понятно 🙂 В конце ролика мы реализуем алгоритм на языке C# и прочувствуем каждый шаг алгоритма в действии. Будет интересно!
Исходный код проекта на GitHub: github.com/codaza/QuickSort
Коллекция List: • C# List
Telegram канал: t.me/codaza
На кофе ☕️: pay.cloudtips.ru/p/179d0532
Patreon: / codaza
Boosty: boosty.to/codaza
0:00 - Начало
0:41 - Смысл алгоритмов сортировки
1:22 - Виды алгоритмов сортировки
2:59 - Тони Хоар - автор алгоритма QuickSort
3:57 - Разделяй и властвуй
4:49 - Концепция алгоритма QuickSort
6:05 - QuickSort в действии
8:40 - Оценка сложности алгоритма QuickSort
11:01 - Реализуем алгоритм на языке программирования C#
20:27 - Завершение
#quicksort #быстраясортировка #алгоритмысортировки #csharp #сишарп #codaza

Опубликовано:

31 май 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 80

@codaza-channel 2 года назад

Удобная навигация по видео :) 0:00 - Начало 0:41 - Смысл алгоритмов сортировки 1:22 - Виды алгоритмов сортировки 2:59 - Тони Хоар - автор алгоритма QuickSort 3:57 - Разделяй и властвуй 4:49 - Концепция алгоритма QuickSort 6:05 - QuickSort в действии 8:40 - Оценка сложности алгоритма QuickSort 11:01 - Реализуем алгоритм на языке программирования C# 20:27 - Завершение

@Spa1ke 2 года назад

За навигацию отдельный плюс видео

@MariMaxVR Год назад

Было бы отлично от вас получить полный курс по C# от новичка до профессионала, будь он хоть платный я бы хотел у вас учиться.

@chinchilla898 2 года назад

Отличный и доступный формат. Ждём новых роликов. Спасибо!

@umatov35 Год назад

Не совсем понятный нейминг в коде, вроде переменная пивот, но в ней хранится самый младший элемент, а сам пивот это array[maxIndex]. А в целом видео супер, спасибо!

@marksreider7645 2 года назад

Спасибо за хорошую подачу материала!

@PAPAKOTT 2 года назад

Выши ролики , это результат огромного труда. Спасибо за это. Очень понятно, доступно и красиво ))). Большое спасибо, ещё раз.

@codaza-channel 2 года назад

Благодарю за тёплый комментарий 🙂 Читая такие комментарии, понимаешь что нужно создавать ролики дальше.

@behemoth1621 Месяц назад

Как и все другие материалы просто шикарны. А есть надежда что будет продолжение канала?

@MrUserNog 2 года назад

О, круто, спасибо! Вы разъяснили именно те моменты которые я не понимал.

@Alex_Beck Год назад

Действительно очень крутая подача!!! Звук, музыка, Анимация. Самое главное очень доходчиво ! Искал сортировку, подписался! Спасибо за видео))) Ждем еще контент! БОЛЬШОЕ спасибо!!!!!!!

@kokon231 2 года назад

Очень хорошее объяснение. Спасибо!

@antonduschak6641 2 года назад

Спасибо большое, очень полезное видео. Долго не мог понять

@vladislavdenisenko7587 2 года назад

Спасибо большое за видео!

@Alkain18 Год назад

Шикарное видео! Спасибо!

@GGFXRDR 5 месяцев назад

обьяснил лучше чем другие ютуберы по этой теме, респект

@HDunno Год назад

Спасибо большое! Хотелось бы увидеть видео про другие алгоритмы и структуры данных. Удачи!

@ym1288 2 года назад

как же круто объяснил!!!

@nikolayvalchanov5686 2 года назад

Спасибо за труд. Очень помогаеш! Продолжай пожалуйста и не забрасывай!

@codaza-channel 2 года назад

Благодарю! Очень рад, что контент помогает 👍

@ym1288 Год назад

вернулся через год чтобы пересмотреть и повторить. супер объяснение :)

@anonim6364 Год назад

зачем я это под ночь посмотрел,теперь весь сон буду обдумывать, а так codaza огромное спасибо

@user-jj9rb9nu2h 2 года назад

Отличное видео! Ждём новых роликов)

@codaza-channel 2 года назад

Спасибо за комментарий. Впереди много интересного 🙂

@user-yt5pl9wk3l 2 года назад

наконец-то попали в мои рекомендации. Спасибо - незаюзанный контент. Спасибо что показываете как код получается на основе черновых набросок а не словно с листка чистовик переписан.

@codaza-channel 2 года назад

Благодарю за комментарий. Надеюсь, информация была полезной 🙂

@johndoe4016qweasd 2 года назад

это просто охренеть насколько крутые видосы (говорю про весь плейлист "Тут станет понятно")! Очень жаль, что забросили по всей видимости(

@tiranbaghdasaryan243 2 года назад

спасибо, очень полезное видео.

@codaza-channel 2 года назад

Благодарю за комментарий. Рад, что информация оказалась полезной 🙂

@Spa1ke 2 года назад

Нужна сортировка одно-, двух-, трёхмерных массивов, было бы полезно посмотреть такое видео

@dad912 Год назад

очень просто .....спс

@PeterCargo Год назад

С 15 минуты по 17 нет звука. А кажется, что там могли быть полезные комментарии по реализации.

@user-xu8dq5nj3e 2 года назад

Деревья выражений было бы интересно посмотреть.

@elmiravzalov5782 2 года назад

Очень хорошо объяснил. Если есть видео про ret и рекурсию, то можно вставить ссылки

@VitVit312 2 года назад

Я: Не могу понять, когда ютуб уже сообразит и начнёт тебя продвигать Ютуб: трясите задом и пускайте цветные сопли !

@codaza-channel 2 года назад

Да, ютуб имеет свои представления)) Спасибо за комментарий, это точно оказывает положительное влияние на продвижение 🙂

@user-ct4xz5on8h Год назад

Упаковка обмена элементами в метод Swap и передача параметров по ссылке, ухудшает производительность быстрой сортировки. Сделал обмен без передачи по ссылке одним блоком кода, сделал серию тестов. Итог передача по ссылке замедляет сортировку на 10 -15%. при сортировке массива на миллион элементов.

@vladislavrazgulyaev2967 2 года назад

привет! расскажи про ENUM....

@user-iv2kz5kh4t 11 месяцев назад

Я буду прав, если скажу, что на 36 строке (for (int i = minIndex; i < maxIndex; i++)) вместо "

@hovikkirishchyan7640 6 месяцев назад

@codaza-channel Объясняешь очень хорошо, но есть деталь, в данной реализации быстрой сортировки выбор опорного элемента не происходит случайным образом. Выбор опорного элемента может действительно повлиять на производительность алгоритма быстрой сортировки. Выбор неэффективной стратегии опорного элемента может привести к плохой производительности, особенно в случаях, когда массив уже отсортирован или почти отсортирован. Например, если опорный элемент всегда выбирается как первый или последний элемент массива, и массив отсортирован по возрастанию или убыванию, комплексность быстрой сортировки может ухудшиться до O(n^2) вместо среднего случая сложности O(n log n).

@Moraru1992 Год назад

🤗

@codaza-channel Год назад

😉

@user-yo7mw6oj4p 2 года назад

А делегаты, события, интерфейсы, IoC и другие страшные вещи разбирать будите?

@codaza-channel 2 года назад

Да, думаю, обязательно поговорим об этом на канале 🙂

@shurale85 2 года назад

ну это далеко не страшные вещи)) куда интереснее tpl, valoltile, Expression

@alexazimov420 2 года назад

Увеличить скорость можно параллельными процессами.

@user-nw8sn5gf9e Год назад

Есть вопрос , зачем результат метода "GetPivotIndex" помещать в переменную соответственно зачем его возвращать. У меня эта функция прекрасно работает с значением void без return pivot; и переменной в которую оно возвращаеться . Я что-то упускаю или это просто для наглядности ?

@user-iv2kz5kh4t 11 месяцев назад

В методе QuickSort происходит ветвление. дикое ветвление)) и для того, чтобы для каждой веточки была своя переменная pivotIndex, метод GetPivotIndex должен её возвращать. Я так понимаю. Но на дебаге этот вопрос не тестил.

@caeswr 2 года назад

супер полезное видео и так мало просмотров

@codaza-channel 2 года назад

Благодарю за комментарий и рад, что информация из ролика оказалась полезной 🙂

@Brometey 2 года назад

Я не совсем понимаю, каким образом мы получаем индекс пивота, есть ли какая-нибудь статья, которую можно прочитать повнимательней ?

@codaza-channel 2 года назад

Более основательно Вы можете ознакомиться с алгоритмом быстрой сортировки на wikipedia: en.wikipedia.org/wiki/Quicksort#:~:text=Quicksort%20is%20a%20divide%2Dand,sometimes%20called%20partition%2Dexchange%20sort. Вот тут еще достаточно подробно демонстрируются шаги реализации алгоритма: www.programiz.com/dsa/quick-sort

@sergeyz.5845 Год назад

По сути мы просто сравниваем все элементы в заданном массиве с последним элементом. И если эти значения меньше или равны последнему элементу, то они перемещаются на позиции перед теми, которые оказались больше последнего элемента. Последний элемент тоже переместится, так как он равен по значению самому себе. Происходит это так: берем элемент, если он меньше или равен последнему, то пивот теперь становится на первую позицию(условно - граница между элементами, которые меньше и больше последнего) Берем второй элемент, например, он оказался больше. Тогда пивот остается на своем месте. И мы уже имеем два отсортированных элемента (второй элемент точно больше первого - мы это проверили). Дальше третий элемент, к примеру, меньше или равен последнему, тогда мы меняем местами второй и третий элемент, потому что второй точно больше третьего(мы это проверяем относительно значения в последнем элементе массива). И таким образом доходим до конца. Последний элемент наконец займет позицию пивота, тк он проходит по условию и равен самому себе.

@sergeyz.5845 Год назад

Здесь одновременно происходит поиск пивота и перемещение элементов

@sawa1976 Год назад

Дико извиняюсь за занудство, но разве цикл не лучше сделать до maxIndex -> for (int i = minIndex; i < maxIndex; i++), один цикл и лишнее сравнение можно сэкономить.

@1ncludecpp656 2 года назад

Пива захотелось

@codaza-channel 2 года назад

🍺

@dad912 Год назад

кстати если реф не ставить - метод сорт будет менять свои значения значения переменных а не значения в массиве - так что работать програмка не будет(((

@syrymzholimbetov8860 Год назад

codazaaaa!) почему аза?) вы наверно уже гдето уже отвечали сори лень искать)

@codaza-channel Год назад

Это вам Хокку на ночь 😉

@robles2145 2 года назад

6:26 важный шаг для понимания алгоритма просто упущен

@codaza-channel 2 года назад

Какой?

@stibushix4779 6 месяцев назад

Наверное тот при котором последний элемент массива оказался сразу на своём месте, под индексом 2. Думаю для наглядности "6" надо было поместить в произвольном месте но не на 3 позиции (индекс 2)@@codaza-channel

@ivanlemming5821 2 года назад

Вы уверены что у вас график логарифма правильно построен?

@codaza-channel 2 года назад

Да. Вас что-то смутило? Взгляните на эту картинку, возможно в сравнении с другими вариантами картина станет яснее: studiousguy.com/wp-content/uploads/2021/06/Complexities-Graph1.png

@juliusmalkov9620 Год назад

ох как ускользнуло - вообще ничего не понял! Что он такой сложный то в понимании!

@codaza-channel Год назад

Попробуйте посмотреть альтернативные источники. Например, на Wikipedia дано достаточно подробное описание: en.m.wikipedia.org/wiki/Quicksort

@dm1tttry 2 года назад

Приходиться ставить скорость 1.25, ну очень медленно говоришь

@codaza-channel 2 года назад

😥

@dm1tttry 2 года назад

@@codaza-channel Извини если расстроил, по контенту все отлично, ты хорош! Наверно, медленная речь стала заметна после твоих Shortов, где ты за 30 секунд излагаешь быстро какую-то тему :)

@olegpol1440 Год назад

Мало что понятно, просто дублируете код словами не объясняя сути алгоритма

@codaza-channel Год назад

Видимо у меня не получилось раскрыть суть алгоритма для вас. Так или иначе, попробуйте посмотреть альтернативные источники. Я могу предложить вам интересную статью, где алгоритм объясняется достаточно подробно: towardsdatascience.com/an-overview-of-quicksort-algorithm-b9144e314a72 Надеюсь, статья окажется более информативной, чем мой вариант изложения. Не стесняйтесь задавать вопросы 🙂

@olegpol1440 Год назад

@@codaza-channel Спасибо, может вернусь к этому видео позже

@bltvg Год назад

Я всё надеялся увидеть реализацию без выделения дополнительной O(n) памяти. Но не увидел. В это вся сложность алгоритма.

@user-oq9xr8dj1b Год назад

Самый быстрый алгоритм упорядочивания массивов разработан мной, только об этом почему-то помалкивают. Я же никто! )) Это только они, вченные, что-то там самое лучшее разрабатывают, а мы типа неспособны и нам не дано. И да, так называемая сортировка пузырьком является частным случаем моего алгоритма сортировки и задействуется в самом конце, когда пару элементов находящихся рядом надо переставить местами. При этом не нужно перебирать весь отсортированный массив, как может показаться знатокам алгоритма сортировки пузырьком. Невозможное возможно. Хоар курит бамбук со своей быстрой сортировкой. Русские способны создавать лучшее. Лишь бы не мешали им создавать эти типа самые умные это лучшее. Свое ценить надо, а не перед иноземным пресмыкаться. На Масковии не самые умные живут. Доказано практикой жизни.

@user-ws7ft5ko6y Год назад

а код можно ?

@user-oq9xr8dj1b Год назад

@@user-ws7ft5ko6y Только за деньги! И так всю жизнь за спасибо проработал и живу как бомж. Разрабатывайте сами, если сможете.

@Vyomantu Год назад

@@user-oq9xr8dj1b Тогда грош цена твоему алгоритму, бомжара. ^__^ Хоар рулит!

@user-oq9xr8dj1b Год назад

@@Vyomantu Пусть рулит. Только лучшим он от этого не становится.

@user-oq9xr8dj1b Год назад

Про сортировку таблиц (массивов массивов) ничего не сказано. Эта тема достойна внимания! Не говорите только, что такого алгоритма нет. Хоар в этой сортировке со своей сортировкой точно курит бамбук.))