Ребят, создаю тред про быструю сортировку. Смотрите. Я понял в алгоритме вот такое: идём по массиву до опорного элемента и сравниваем каждый элемент слева и справа с опорным, Если элемент слева меньше или равен опорному - идём дальше и до тех пор, пока не найдём элемент, который больше опорного. Тоже самое справа. идём к опорному, пока не найдём элемент, который меньше опорного. Если с двух сторон такие нашли - свопаем их. Вот. И вот так идти, пока эти два указателя не пересекутся. Ок. теперь передаём в эту же саму функцию те части массива, которые слева и справа от опорного и повторяем всё.Допустим массив из трёх элементов 4 1 3.слева элемент больше чем опорный. значит тут указатель слева останавливается. справа элемент больше опорного, значит этот указатель декрементируем и встаёт он на опорном. свопаем 4 и 1. дальше оба указателя перегоняют друг друга и тут цикл завершён. я не понимаю ребят. получилось 1 4 3. Не отсортирован. Как дальше то? Объясните мне чего я не так понимаю в алгоритме.
>>763831 (OP)>4 1 3На подмассивах длинной меньше шести используется пузырек.
>>763844В алгоритме нет такого.
>>763894Алгоритм != практическая реализация.>>763844Обычно еще лучше - quicksort с лимитом на глубину рекурсии, а дальше переключение на heapsort.
>>763906Ну погоди. Я не понимаю. Это реально чтоль так работает? Как-то тупо
>>763908А как ты хотел, чтобы там rocket science был? Фактически сейчас рулят два алгоритма с вариациями - introsort (эта та смесь quicksort и heapsort) и timsort (ее в пистоне прикрутили, она теоретически еще быстрее, но там свои проблемы есть, например, уже находили некорректно сортируемые наборы).
>>763917Понимаешь, я её должен реализовать не для того, чтобы в каком-то проекте юзать, в котором сортировки надо делать, на каком-то этапе работы, а для того, чтобы придти так мягонько и преподу показать, что вот я сделал. И я не понимаю как вообще алгоритм потенциально может работать с массивом из трёх. Я вот не видел нигде предупреждения о том, что этот алгоритм не применим для такого вот массива.
>>763922Он может же. На любой итерации ты получаешь один центральный элемент + еще два массива (возможно, пустых), к которым применяешь рекурсивно. Если тебе пришел пустой массив или массив из одного элемента, то ты просто сразу возвращаешь его. Вот и все.
>>763924в примере, который я приводил в конце осталось 1 4 3. в центре стоит 4, слева и справа массивы 1 и 3. как я переставлю центральный и правый местами? не ну если бы я мог передать этот подмассив вместе с опорным элементом, тогда я мог бы переставить .а так я как это сдлеаю? я не понимаю вот этого вот. объясни пожалуйсьа.
>>763936блять, тебя учили пользоваться дебагером? Зайди в вижлу, копирни код сортировки и дай ей на вход массив, а потом дебагером походи, сразу увидишь всё сам.
>>763941>вижлуВ свою идесамофикс
>>763936>слева и справа массивы 1 и 3"лево и право" это больше-меньше опорного.В твоем случае это " " и "4 3".
>>763941смотри. ща.https://habrahabr.ru/sandbox/29775/вот тут реализация вот такая. я так понял тут почан передаёт подмассив вместе с опорным элементом на обработку. т.е. в примере как у меня, в его реализации, будет на один больше рекурсивных вызовов. но это же не по алгоритму так передавать вместе с опорным элементом, не? я вот и запутался. с другого сайта брал реализацию, так там вообще пинцет массив не отсортировался как надо.
>>763946опорный же задаётся индексом, а не значением, не?
>>763952>с другого сайта брал реализациюТам проебали равенство, Люк.
>>763957всмысле? (зачем ты сажей льёшь? мне ведь не помогли даже ещё)дайте реализацию на си, которая по вашему мнению правильная хоть.
>>763954Какое это имеет значение?Для следующей итерации он не нужен. Нужны две пары индексов левый мин-макс и правый мин-макс индексы.Они сразу есть и равны i, j после выхода из основного цикла по while(i<=j).САЖА
>>763831 (OP)"Алгоритмы построение и анализ" именно с этого же и начинается, разве нет?
Тут дело в том, как считать границы массива. Имеем массив 4 1 3, передаём его в функцию сортировки. Получаем 1 4 3. Передаём части массива дальше - левая часть 1 4, правая 4 3. После этого правая часть отсортировывается до 3 4, и весь массив выглядит как 1 3 4 (потому что мы передаём индексы, а не делим массив физически), и части массива передаются дальше. Левая-левая часть 1, левая-правая часть 3, правая-левая часть 3, правая-правая часть 4. Один элемент всегда отсортирован, поэтому все ветви завершаются.
