Алгоритмы и структуры данных 6. Быстрая сортировка.
ฝัง
- เผยแพร่เมื่อ 20 ก.ค. 2024
- Алгоритмы, структуры данных, программирование
В видео подробно рассматриваются еще один алгоритм сортировки - быстрая сортировка.
Если видео Вам понравилось, вступайте в группу vk: dsysoevprog
Подписывайтесь на страничку в facebook: / dsysoevprog
Полезные ресурсы:
1. Портал университета ИТМО, посвященный алгоритмам и структурам данных: neerc.ifmo.ru/wiki/index.php?t...
2. Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ. (Книга, легко гуглится)
Шикарное объяснение, спасибо Вам.
Спасибо Вам, все понятно)
Круто. Спасибо.
Лучшее объяснение, что я видел. Спасибо!
+
Объясняете очень понятно)
Привет!
Мне нравиться твоя подача материала.
И хочется, чтобы ты разобрал:
1. Алгоритмы на графах
2. Бинарные деревья, черно-красные деревья
3. Разобрать бы кучу
4. Жадные алгоритмы
Лучшее пояснение из тех что нашёл!)
Спасибо)
Огромное спасибо!
Я вот не пойму, когда индексы сходятся посередине получается мы меняем одно и то же число само на себя
Базовый случай рекурсии не сработает, если придет пустой массив. Поэтому корректный базовый случай можно сформулировать как: массив с одним элементом или пустой массив. Нет?
Да, вы абсолютно правы. Этот случай я упустил из виду.
Хорош, спасибо
Спасибо!
Спасибо. Википедия и ещё чей-то перевод не дали понимания. Вы наглядно объяснили алгоритм, и теперь я его никогда не забуду.
Что за "О большое"? (Ладно, матан сам изучу)
там от матана ничего нет
Ничего не понятно, но очень интересно)
Представленный алгоритм некорректный, если опорный элемент будет самым минимальным то уже на первом этапе мы не сможем перемещать элементы.
В видео на 2 этапе если массив был бы [ 5, 1, 2 , 6] 5>1 и 6>1, 5>1 и 2>1. получается ничего не перемещаем.
Вы неправы. Согласно описанному алгоритму будет происходить следующее.
5 >= 1, соответственно L останавливается на 5, дальше R движется влево, проходит 6 и 2 и останавливается на 1, т. к. 1
Помогитееее
Почему для [2 9 0 -100 50 4 -2] не работает?
почему на 3:36 у тебя L + R \ 2 это восемь? Почему в 2. числа перепрыгнули и теперь в L + R \ 2 единица вообще?
1. Потому что в средней ячейке оказалась восьмерка. Пример такой. На другом примере могло бы быть другое число.
2. На втором рисунке показана конечная конфигурация, которая получается после распределения элементов согласно описанному правилу.
Отличное видео, тут еще по сортировке видео: th-cam.com/video/M6iMFWxExAU/w-d-xo.html
Зачем нужен L элемент если он всегда в массиве по нулевому индексу?
Он по нулевому только на старте. Потом может меняться.
Не корректную версию квиксорта автор предоставил. На иных значениях представленный алгоритм не до конца сортирует
Прошу привести пример такого набора данных, и на каком этапе алгоритм сломается.
@@DanilaSysoev Алгоритм действительно изложен некорректно. Вы упустили ситуацию с равенством опорного элемента и текущего сравниваемого. Казалось бы, что может быть проще, добавить знак равно в одно из сравнений. К примеру, когда мы идем слева на право мы ещем элементы, которые больше опорного, а когда идем с право на лево - элементы меньше, либо равно опорному.
А теперь попробуйте применить этот алгоритм для сортировки массива [2, 3, 4, 7, 5, 6, 1]. Для первого прохода по вашей методике выбран опорный элемент 7. Как отработает ваш алгоритм?
P.S. Я сам работал преподателем в вузе и понимаю что там не хватает практики. Поэтому я рекомендую писать на все тести. Попробуйте взять любой язык программирования и сгенерировать массив на 1000 элементов, а после сортировки пройти в цикле и проверить, что каждый элемент меньше следующего.
@@n1k1ta73
Отвечая на вопрос, как отработает алгоритм - он отсортирует массив.
Вот поэтапный разбор процесса сортировки
2 3 4 [7] 5 6 [1] - опорный 7
l r
2 3 4 1 5 6 7
r l
-----------------
2 3 [4] [1] 5 6 - опорный 4
l r
2 3 1 4 5 6
r l
-----------------
2 [3] [1] - опорный 3
l r
2 1 3
r l
-----------------
[2] [1] - опорный 2
l r
1 2
r l
Итог
1 2 3 4 5 6 7
(4 5 6 не расписывал, там все упорядочено и не будет перемещаться)
@@n1k1ta73 Вы, вероятно, не очень внимательно смотрели видео. указатели справа и слева останавливаются на элементах >= и
Как найти границу разбиения? До меня всё не доходит.
Как мы поняли из урока, то те элементы которые больше опорного элемента, они собираются справа от опорного элемента, а те которые меньше либо равны, те собираются левее от опорного элемента. Скажу так. Там где закончилось число которое меньше(либо равно) опорного, и там где начинаются числа больше опорного, вот это и есть граница разбиения.
Граница разбиения = (L+R)/2, т.к индексация массива начинается с нуля и L=0 и R=7 соответственно, то (L+R)/2=3.5 (далее идет округление в меньшую сторону). Получается индекс массива равен 3, а в этой ячейке число 8.
Жаль, что забросил канал
В ближайшее время выход видео на канале будет возобновлен.
@@DanilaSysoev хорошая новость.