Реализация QuickSort (включение или исключение сводного элемента во время разделения)
Я пытаюсь разобраться в алгоритме быстрой сортировки. Я пробовал разные реализации. Проблема, с которой я столкнулся, связана с включением/исключением поворотного элемента.
Рассмотрим эти три реализации.
Этот код вызовет ошибку в коде VS, и код VS просто остановится. Обратите внимание, что элемент поворота (
ind) включается вleftтолько один раз (по крайней мере, мне так кажется) и не добавляется отдельно в последней строке функции:def quick_sort(arr): if len(arr)<=1: return arr ind = arr[0] left = [i for i in arr if i <= ind] right = [i for i in arr if i > ind] return quick_sort(left) + quick_sort(right)Если я исключим
indизleft(используя<вместо<=) и добавлю[ind]в последней строке, это сработает. НО в отсортированном списке не будет дубликатов исходного списка:numbers = [5, 2, 3, 2, 7] print("Sum of numbers:", quick_sort(numbers)) def quick_sort(arr): if len(arr)<=1: return arr ind = arr[0] left = [i for i in arr if i < ind] right = [i for i in arr if i > ind] return quick_sort(left) + [ind] + quick_sort(right)Наконец, эта реализация отлично работает, правильно сортируя все значения. НО я не понимаю, в чем разница между этой реализацией и первой. Почему первый вызывает ошибку, а этот работает? Но в обоих случаях мы включаем опорную точку (
ind) только один раз?numbers = [5, 2, 3, 2, 7] print("Sum of numbers:", quick_sort(numbers)) def quick_sort(arr): if len(arr)<=1: return arr ind = arr[0] left = [i for i in arr if i < ind] middle = [i for i in arr if i == ind] right = [i for i in arr if i > ind] return quick_sort(left) + middle + quick_sort(right)
Я проверил предыдущие вопросы и ответы по этой теме, но ничего по этой проблеме не нашел.
Спасибо за ваш ответ! Проблема заключалась в том, что для меня № 1 и 3 выглядели одинаково, потому что оба включают в себя поворотный элемент. Но, очевидно, я упустил из виду, что этап, на котором мы включаем этот элемент, имеет значение, поэтому в № 1 мы передаем left+pivot рекурсивному вызову, а в № 3 мы избегаем этого и при необходимости добавляем элемент поворота на более позднем этапе.
Ответы 1
Реализация №1 будет страдать от бесконечной рекурсии, когда left принимает все значения в заданном списке (а right остается пустым). В этом случае прогресса нет, и рекурсивный вызов снова решит ту же проблему, что приведет к тому же повторному рекурсивному вызову... и т. д. Это происходит, например, с вводом [2, 1].
Вы уже правильно определили проблему со второй реализацией. Если сводное значение имеет дубликаты, они удаляются из результата. Эту проблему решает третья реализация.
И вторая, и третья реализации решают проблему, с которой сталкивается первая реализация: гарантировано, что рекурсивные вызовы будут иметь дело со строго более короткими списками, поскольку гарантировано, что одно или все значения сводки больше не являются членами списка, который передается рекурсивному вызову.
Не имеет отношения к вашему вопросу, но быстрая сортировка обычно реализуется как алгоритм на месте, т. е. без создания новых списков во время процесса. Вместо этого данный список видоизменяется посредством свопов. См. Википедию о быстрой сортировке.
Спасибо за быстрый ответ! Позвольте мне уточнить. Означает ли это, что в №3 мы обязательно исключаем опорный элемент из левого списка, а затем отдельно добавляем его на более позднем этапе алгоритма, если какие-то элементы ему равны? В этом случае мы включаем элемент поворота, но избегаем его использования на этапе рекурсии. Это верно?
Да это верно. В #3 и left, и right гарантированно будут короче arr, поскольку мы откладываем вхождения опорных значений (они не включены ни в left, ни в right) для добавления между двумя отсортированными результатами, которые мы получаем из рекурсии.
Еще раз спасибо, это было очень полезно! Я думал, что понял это, но потом подумал, что если мы выберем средний элемент в качестве опорного элемента (len(arr)//2), а затем включим его в левый (используя <=), он снова перейдет к бесконечной рекурсии. Но в этом случае подмассив делится при каждом вызове и, следовательно, становится меньше, даже если мы включили опорную точку. Как же тогда? я смущен
«Но в этом случае подмассив становится... меньше»: вы все равно рискуете, что выбранный стержень (из середины) будет наибольшим значением в массиве. Неважно, откуда вы берете опорную точку: если есть риск, что это наибольшее значение, вы все равно рискуете, что все значения в массиве попадут в левый раздел. Тривиальный пример: у вас есть arr=[1,1,1,1,1,1]. Неважно, какую единицу вы возьмете в качестве опорной (среднюю, левую или...), вы всегда будете заполнять left всеми этими значениями.
Еще раз большое спасибо, я понял это, основываясь на вашем предыдущем ответе. На этот раз я пропустил, что во время разделения, если все числа в подмассиве меньше или равны стержню, не только числа не изменятся и не перейдут в левую часть, но ПОРЯДОК останется прежним, поэтому средний элемент также будет оставайся таким же. Теперь ясно, что он застрянет в бесконечной рекурсии. Надеюсь, на этот раз мое понимание окончательное :) Ваш ответ был очень полезен.
В версии №1, если опорная точка оказывается самым высоким значением в списке, то
leftв конечном итоге содержит ВСЕ, и вы вызываетеquick_sort()с точно тем же списком, что и раньше - что, конечно, снова делает то же самое, поэтому у вас есть бесконечное количество рекурсия. Чтобы рекурсия работала, каждый вызов должен быть строго ближе к базовому (нерекурсивному) случаю.