Java. Быстрая сортировка. Объяснение на пальцах)
Вставка
- Опубліковано 15 бер 2019
- Как работает быстрая сортировка и почему она быстрая? Разбор алгоритма и небольшой сравнительный тест производительности.
Исходники:
github.com/Arhiser/java_tutor...
Поддержать канал💰:
yoomoney.ru/to/410018856244871
#ArhiTutorialsJava #ityoutubersru
Спасибо, сколько пересмотрел видео по алгоритмам, у вас прям самое доходчивое объяснение в русском ютубе
Спасибо большое за объяснение, всё очень доходчиво, спасибо за ваш труд!)
Спасибо! Очень доступно объясняете.
Очень хороший пример сравнения с сортировкой пузырьком! Спасибо, Сергей, очень познавательно!
Супер! Сергей, спасибо за показательное сравнение Quick sort and Bubble sort! Получилось очень наглядно!
Спасибо большое за уроки, очень понятно объясняете, и код логичный и легко воспринимается!!! Сначала нашел видео по деревьям, нужно было, а потом завис на всем плейлисте по алгоритмам))) Сначала думал просто пересмотрю, но по ходу захотелось и код повторить!
я видел алгоритмы на youtube, но таких подробных глубоких разборов, как у вас на других каналах нет
Спасибо! Интересный пример)
Спасибо большое!
Не думал, что фраза на пальцах ))) была буквальной ))))
Супер!
Спасибо за видео, очень полезное) сталкивался в интернете с информацией, что если много одинаковых элементов, то нужно разделять массив на 3 части. Для меньших, для больших и для равных значений. В данном коде так же нужно, или перестановка решает эту проблему?
Я читаю Стивена Родса Алгоритмы и структуры данных Теория и практика. А так же смотрел видео от Гарварда про быструю сортировку и я могу сказать что есть множество способов реализовать данный алгоритм. Твой более понятный так как он подкреплен кодом и объяснениями со стороны человека по отношению кода. Дальше я могу нарисовать приблизительный рисунок работы данного алгоритма.
Спасибо!
Рад, что пригодилось. Спасибо за отзыв!
Очень полезно
лучшее видео
Отлично! Очень похоже на бинарный поиск)
я бы не сказал, бинарный поиск работает уже на сортированом массиве
@@Das.Kleine.Krokodil тем не менее сходство есть
@@user-mt9kf4mi7x сходство в том что относится к семейству алгоритмов "Разделяй и властвуй"
Подскажите а если я хочу реализовать крайний правый то что я должен изменить в вашем исходнике?
Sergey ti krasavchik
thanks
Огромное спасибо! все более чем понятно. Можно вопрос, я вот у вас случайно увидел метод (measureTime()), который подсчитывает время работы алгоритма. Не могли бы вы пожалуйста показать код метода, хотелось бы посмотреть подробнее. Спасибо.
Конечно.
private static void measureTime(Runnable task) {
long startTime = System.currentTimeMillis();
task.run();
long elapsed = System.currentTimeMillis() - startTime;
System.out.println("Затраченное время: " + elapsed + " ms");
}
Тут просто запоминаем время до начала выполнения, потом выполняем task.run(), потом берем время после окончания выполнения task.run() и печатаем разницу.
Удобно, так как можно один раз написать такой метод, а потом измерять им все что угодно)
Спасибо еще раз! действительно удобно и универсально. Я написал что-то похожее, но у вас получилось интереснее.
11:55 Расскажите, пожалуйста, почему вычисляем индекс среднего элемента по такой формуле, а не просто (from + to) / 2? В чём хитрость?
(from + to) может вылезти за диапазон допустимых значений int-а (максимальный_int = 2147483647). Например если from будет 2*10^9, а to будет 2,1*10^9
Код в примере перестаёт корректно сортировать неотсортированный массив если опорный индекс указать ( from + (to - from) / 2 ).
Хорошее видео, очень подробно) Может и банальный вопрос, но что посоветуешь прочитать на этапе «уже не новичок, но и не среднячок»)))
Сложно сказать. А что уже читали?)
ищи хорошие лекции вузовские
Сергей, а в чём смысл рекурсивно делить массив на подмассивы? Я так и не понял. Я прочитал Адитью с его гроканием алгоритмов, так он связывал это со стеком вызовов, типа стек короче получается. Хочется спросить, и шо? Короче, и что из этого? И почему подмассивы обрабатываются параллельно, если в конечном итоге рекурсией всё вызывается последовательно?
После первого разделения из одного массива получаем два. Эти два массива сортируются независимо друг от друга .То есть получаем две независимые задачи по размеру меньше чем исходная.
Сортировать два маленьких массива - это быстрее чем один большой.
Пусть исходный массив длинной 100 элементов, мы поделили его на 2 массива по 50 элементов и положим для примера, что мы используем алгоритм сортировки с временной сложностью O(n^2).
Итого имеем
сортировка целого массива:
100^2 = 10000 условных операций
сортировка двух половинок массива:
50^2 + 50^2 = 5000 условных операций
Таким образом, разделение массива на две части ускорило сортировку в 2 раза.
А быстрая сортировка продолжает делить массивы дальше, по этому выигрыш еще больше.
Благодарю вас за объяснение.
Подскажите пожалуйста, если я споткнулся об рекурсию, не могу понять ее на более сложных, как эта сортировка, примерах, то стоит ли дальше изучать язык программирования?
С факториалом и числами Фибоначчи рекурсия понятна.
Конечно стоит! Все в начале не понимают, это нормально. Программирование сильно отличается от другой деятельности и мозг не готов сразу воспринимать сложные незнакомые абстракции. Со временем все придет, если не бросать.
Говорят есть программисты от рождения, которые сразу все понимают. Но я таких не встречал, и сам тоже не такой)
Sergey Arkhipov благодарю вас за мотивационный пендель 😸!
числа Фибоначчи не стоит искать при помощи рекурсии. Это очень не эффективный алгоритм. Для поиска 100-го числа Фибоначчи при помощи рекурсии понадобится около 50 000 лет))
@@jeoparrdy сам подщитал?
@@MsDima9999 можешь сам проверить
Хорошее объяснение. Но зачем Вы изобретаете велосипед в виде метода arraysToString? есть же Arrays.toString(array)
Да, есть у меня такая проблема. Память не очень, видимо это последствия работы в IT)
ua-cam.com/video/PveuJ8hy_qg/v-deo.html
Привет. Интересное видео, но не мог бы ты подсказать, что делать если нужна вариация быстрой сортировки, которая делиться на три массива. Был бы очень благодарен.
зачем именно такая нужна?
@@Das.Kleine.Krokodil не помню уже, год назад было нужно для курсовой
А почему тест подробнее не объясняете, что за метод measureTime()? Откуда он, у меня идея его не принимает?
Но у меня есть пару вопросов по конкретным участкам алгоритма.
Здравствуйте, а скажите пожалуйста, как у вас получается открывать массив в консоле пошагово, у меня только мой массив и отсортирован. Буду очень благодарен.
Для этого служит функция, которая есть в исходниках
github.com/Arhiser/java_tutorials/blob/master/src/ru/arhiser/sort/QuickSort.java
Функция:
private static void printSortStep(int[] arr, int from, int to, int partitionIndex)
Ее надо вызвать в основной функции сортировки quickSort после строки
int divideIndex = partition(arr, from, to);
передать в нее состояние на текущем шаге
printSortStep(arr, from, to, divideIndex)
а она уже все напечатает.
@@arhitutorials Спасибо огромное. Мне как новичку, очень помогают ваши уроки и ваши ответы.
Там где идёт первое спнение на меньше , сравнивается элемент сам с собой на меньше и соответственно даст фолс и не зайдет в блок - инкрементация не произойдет и пиздец ...спасибо !!
вот тоже долго не мог понять, думал может я что-то не догоняю
Привет. Спасибо за видео.
Сколько у тебя лет опыта в Android разработке и вообще в программировании?
Привет. В программировании лет 15. В Android разработке где-то 9 лет. До андроида немного писал на c++, по большей части занимался web-разработкой. Web мне не понравился, так как верстка - это скучно, js фреймворки учить - неблагодарное занятие) По этому перешел на android и доволен.
@@arhitutorials Круто. Спасибо, что делишься своими знаниями.
@@arhitutorials Сергей, а насколько сейчас высокие требования для Junov в Android разработке?
@@funnymoment9164 знания это такая вещь, если ими делишься, у тебя от этого меньше не становится. По этому сам делюсь и других призываю к этому)
@@funnymoment9164 Требования достаточно высокие. Часто дают тестовое задание сделать небольшое приложение, которое взаимодействовало бы с сервером через RESTful API и отображало приличный пользовательский интерфейс. Еще требуют применить какой-нибудь архитектурный паттерн типа Model-View-Presenter или Model-View-ViewModel. Часто просят знание языка Kotlin, что большой проблемой не является.
В общем, прежде чем устраиваться, надо самостоятельно написать хотя бы парочку приложений, чтоб получить хорошее представление, как оно работает и из чего состоит.
По какой причине может выдавать ошибки в 20 и 22 строках? partition и printSortStep выделяются красным
А, все понял, нужно дальше код прописать)
Неудачно выбрал индекс опорного элемента. Долго не мог понять твой код, особенно первый рекурсивный вызов с to который меньше from и первый while. Взял бы pivot[l + r] , было бы гораздо понятнее
в чем неудачность?
P.S Моежете в будущем предоставлять исходники кода без всяких дополнений ? просто хоть и я получил ваш исходник но удалять определенные части кода я боюсь хоть они мне и не нужны. Так как я нууб и не шарю и боюсь в этом случае нарушить фнкциональность кода.
Хорошо. Чтоб работало нужны функции quickSort(), partition() и swap(). Остальное можно выбросить.
стоп стоп стоп,тоесть ты учил быструю сортировку и ее реализацию на джаве,но боялся что-то удалять из кода чтобы не нарушить чего либо емм серезно?
@@MsDima9999 я забросил программирование как таковое, но если говорить про быструю сортировку, то я её изучил посмотрев видео англоязычного ютубера который очень хорошо разобрал её работу на псевдокоде с куче картинок как она вообще работает а потом показал минималистичный вариант реализации на C/C++ с использованием базового синтаксиса. А добивающим было когда я прочел главу по быстрой сортировке от Лабофаре на java. Тут реализация базового синтаксиса с C/C++ на java из книги была самый раз, но я так еще и не изучил последний раздел быстрой сортировки, анализ среднего случая работы быстрой сортировки, тут я туп и ленив так как анализ алгоритмов от джона маконелла для меня трудна. Но я сейчас забросил учебу программированию(дискретная математика. алгоритмы и структуры данных, прочие разделы Computer science.)
@@sainthentai7763 почему закинул программирование?
@@MsDima9999 как бы так сказать, у меня жизнь жопа в плане самоорганизации, планировании, работе, я большую часть времени прокрастинирую и сижу безработным постоянно в депрессии. Ну как то так
Я тут посмотрел на пару алгоритмов реализации быстрой сортировки и заметил кое что странное, почему сравнение идет по отношению индексов ? Короче почему мы на 45 строчке мы написали так if ( left_Index
if (leftIndex pivot) {
rightIndex--;
}
@@arhitutorials так по этому условию как раз таки будут меняться элементы при leftIndex == rightIndex
@@arhitutorials и сможете ли вы объяснить зачем в условии while (leftIndex
@@arhitutorials не очень изящный алгоритм получается из-за озвученных мной двух моментов.
@@MrSBFI почему бы Вам просто не убрать "лишние" операторы и увидеть своими глазами, что получится)
15.10.2022
никого не смущает while в while и соответственно сложность n^2?
У меня на этом коде получился такой результат:
Случайный массив
Быстрая сортировка: 9367 ms
Сортировка слиянием: 10961 ms
Отсортированный массив
Быстрая сортировка: 3048 ms
Сортировка слиянием: 4780 ms
Получилось, что разница между быстрой сортировкой и сортировкой слиянием практически никакой и этот результат стабилен.
эту сортировку я знаю
Сложновато)
Было интересно. Но смотрю, что сортировками упарывается всего 180 человек. :)
Код непонятный.
не стоит делать while (pivot > data[start + (end - start)] / 2)
в ряде случаев приведет к бесконечному циклу
Спасибо!
Спасибо!