В этом видео мы рассмотрим слабости быстрой сортировки, которую мы написали в прошлом видео. Затем мы улучшим сортировку улучшив алгоритм выбора опорного элемента.
Ребят В коде есть незначительная ошибка Я опечатался и увеличил глубину на 2 в batyaQuickSort Код можно посмотреть, позапускать и поэкспериментировать по ссылке: scastie.scala-lang.org/rbjCuWJZRnCOJy1Membp3A
@a.khakimov
3 жыл бұрын
Отлично разложил по полочкам
@user-sq6iu5nn3h
3 жыл бұрын
Во 32 строке ты вроде прибавляешь к d+2, хотя вроде нужно d+1
@wolf_code
3 жыл бұрын
метко подмечено, согласен это ошибочка) в закреп комменте как раз я это имел ввиду
@vperepelkin
2 жыл бұрын
Основной недостаток quicksort - это неустойчивый (unstable) алгоритм. Сортировка называется устойчивой, если порядок записей с одинаковыми ключами после сортировки сохраняется. Очевидно, что если Вы сортируете массив чисел, то устойчивость алгоритма неважна (одно число 10 от другого 10 неотличимо). Для сортровки записей (структур) это не так (хотя зависит от прикладной задачи).
@wolf_code
2 жыл бұрын
Можно написать устойчивый quicksort думаю
@wolf_code
2 жыл бұрын
Даже эта реализация кстати устойчивая
@a.khakimov
3 жыл бұрын
результат list.length лучше сохранить в константу
@wolf_code
3 жыл бұрын
я точно не помню, list.length бегает по списку? тогда - согдасен есть смысл вынести. спасибо - отличное замечание
@profesor08
2 жыл бұрын
Так как ты рандомно выбираешь три числа из всех доступных, то остается ненулевой шанс, что алгоритм выдаст глубину рекурсии 1000. Достаточно скормить сортированный массив и много удачи. А все потому что есть шанс что для каждой рекурсии будут выбираться три одинаковых числа, и при этом они будут самыми неудачными.
@wolf_code
2 жыл бұрын
Какова вероятность такого события?
@profesor08
2 жыл бұрын
@@wolf_code Раз надо три раза подряд и количество не меняется, то (1 / n) * (1 / n) * (1 / n) для каждой итерации и потом все перемножить, где n - количество чисел на каждой итерации.
@HideDJeker
2 жыл бұрын
@@wolf_code а какова вероятность, что вам попадется обратно отсортированный массив? Чтобы этого избежать можно брать элемент по центру и 2 случайных элемента из правой и левой стороны относительно центрального, тогда мы точно избегаем коллизий. Ну и что то наверное можно придумать если элементы равны(брать центральный индекс или ближайший). В общем то все оптимизации склонны к предотвращению кейса когда происходит деление на N-1 и 1 элемент. В интернетах еще пишут, что можно просто найти медиану для опорного эл-та, но по идее её поиск точно так же N^2 в худшем случае.
@wolf_code
2 жыл бұрын
@@HideDJeker в сортировке из либы джава берется 7 элементов равномерно удаленный друг от друга и вычисляется медиана среди них, а если массив меньше 7 элементов - он сортируется сортировкой вставками т к для таких размеров она быстрее я это к тому что на практике очень частно комбинируют разные типы сортировок
@HideDJeker
2 жыл бұрын
@@wolf_code круто, а я все думал как это они медиану считают если это уже N. Спасибо.
@nikoluk7109
2 жыл бұрын
А можно ли сделать код ссылочно прозрачным? Грубо говоря так как вы пользуетесь генератором случайных чисел то глубина рекурсии может отличатся от запуску к запуску (то есть код не чистый) Но для детерминированного варианта всегда есть худший случай.
@wolf_code
2 жыл бұрын
А почему если глубина рекурсии разная - то код нечистый? То что я использую случайные числа - вот где СП нарушается, можно избавиться от рандома и просто брать 7 элементов из массива (так сделано в библиотечной версии сортировки в джава)
@nikoluk7109
2 жыл бұрын
@@wolf_code Глубина рекурсии получается разная в следствии того что используются случайные числа (я это и имел ввиду). Так как она может получится разная то и функция не чистая: на один и тот же вход может дать разный выход. Да, брать фиксированное количество из массива выход: вопрос откуда же их из массива брать.
@alexandergrigorev4518
2 жыл бұрын
Я думаю он просядет на массиве из одинаковых элементов
@wolf_code
2 жыл бұрын
На таком массиве он отработает за линейное время
@MichailLLevin
Жыл бұрын
Зачем эти гадания? Контролируем глубину, если стала больше чем 2log n - вызываем сортировку кучей (пирамидой), у неё сложность гарантированно n*log n, только константа хуже
Пікірлер: 22