При реализации быстрой сортировки необходимо следить, чтобы длины подмассивов после разбиения были строго меньше чем длина разбиваемого массива.
Передадим массив arr == {1, 3, 2}
в вашу сортировку. В качестве опорного значения mid
будет выбрано число 3
. В подмассив left
будут помещены все значения меньше либо равные опорному значению. Т.е. left == {1, 3, 2}
. В подмассив right
будут помещены все элементы большие, чем опорный элемент. Так как в массиве arr == {1, 3, 2}
таких элементов нет, то массив right
будет пустым.
Затем функция qsor
вызывает себя, передавая в качестве аргумента массив left = {1, 3, 2}
. Всё повторяется снова. Функция будет вызывать рекурсивно себя до тех пор, пока не исчерпает стек.
Как вариант можно разбивать исходный массив не на два подмассива, а на три: элементы меньшие опорного, элементы большие опорного и элементы равные опорному. Затем сортировать только меньшие и большие элементы.
Пример:
#include <vector>
#include <cstddef>
std::vector<int> qsor(std::vector<int> arr)
{
if (arr.size() < 2)
return arr;
std::vector<int> left;
std::vector<int> right;
std::vector<int> middle;
int mid = arr[arr.size() / 2];
for (std::size_t i = 0; i < arr.size(); i++)
{
if (arr[i] < mid)
left.push_back(arr[i]);
else if (arr[i] > mid)
right.push_back(arr[i]);
else
middle.push_back(arr[i]);
}
left = qsor(left);
right = qsor(right);
left.insert(left.end(), middle.begin(), middle.end());
left.insert(left.end(), right.begin(), right.end());
return left;
}
У представленной выше реализации быстрой сортировки есть два серьёзных недостатка.
Во-первых, опасность переполнения стека всё ещё сохраняется. В худшем случае функция сортировки будет разбивать массив длины n
на три подмассива с длинами n-1
, 1
и 0
. При каждом рекурсивном вызове длина большего подмассива может получаться всего на единицу меньше, чем длина сортируемого массива. В таком случае, глубина рекурсии будет пропорциональна длине исходного массива.
Во-вторых, в худшем случае понадобится O(n**2)
дополнительной памяти для хранения подмассивов.
Первый недостаток можно решить устранением одного из рекурсивных вызовов. Меньший из подлежащих сортировке подмассивов необходимо сортировать с помощью рекурсивного вызова, а больший подмассив следует сортировать в текущем вызове функции. Тогда максимальная глубина рекурсии в худшем случае будет пропорциональна log(n)
, где n
— длина исходного массива.
Второй недостаток решается сортировкой на месте. Нет никакой необходимости создавать дополнительные подмассивы. Достаточно перемещать элементы сортируемого массива на нужные позиции непосредственно в сортируемом массиве.
К тому же не помешало бы в качестве опорного элемента выбирать что-нибудь посложнее, например, медиану из первого, среднего и последнего элементов. Такая стратегия не исключит вероятность наступления худшего случая, но уменьшит.
Пример:
#include <utility>
#include <iterator>
#include <functional>
template <typename RandomIt, typename Compare>
void qsort(RandomIt first, RandomIt last, Compare comp)
{
using std::swap;
while (true)
{
auto dist = std::distance(first, last);
if (dist <= 1)
return;
auto& first_val = *first;
auto& last_val = *(last - 1);
if (dist == 2)
{
if (comp(last_val, first_val))
swap(last_val, first_val);
return;
}
auto middle = first + dist / 2;
auto& middle_val = *middle;
if (comp(middle_val, first_val))
swap(middle_val, first_val);
if (comp(last_val, first_val))
swap(last_val, first_val);
if (comp(last_val, middle_val))
swap(last_val, middle_val);
if (dist == 3)
return;
swap(first_val, middle_val);
auto inc_first = first;
auto dec_last = last - 1;
while (true)
{
do
++inc_first;
while (comp(*inc_first, first_val));
do
--dec_last;
while (comp(first_val, *dec_last));
if (inc_first >= dec_last)
break;
swap(*inc_first, *dec_last);
}
if (inc_first - first > last - inc_first)
{
qsort(inc_first, last, comp);
last = inc_first;
}
else
{
qsort(first, inc_first, comp);
first = inc_first;
}
}
}
template <typename RandomIt>
void qsort(RandomIt first, RandomIt last)
{
qsort(first, last, std::less<typename std::iterator_traits<RandomIt>::value_type>());
}
arr
который никак не меняется. Плюс к этому у вас постоянная рекурсия, т.к после цикла либоleft
либоright
будет содержать хотя бы один элемент. – Rikitikitavi 1 окт '20 в 3:28