Если я правильно понял проблему, то она заключается в том, что я не ставлю некоторые числа на правильное место. Но я не знаю, как исправить эту проблему.
std::vector<int>::iterator partition(std::vector<int>::iterator left,
std::vector<int>::iterator right,
int elem) {
// Проверка вроде как бесполезная, но все же поставил
if (left == right) {
return left;
}
while (left != right) {
// двигаю левый итератор до того момента, пока он меньше elem
while (*left < elem) {
++left;
if (left == right)
return left;
}
// Двигаю правый итератор, пока он меньше elem.
// Проблема скорее всего здесь, так как случай равенства elem не обрабатывается
while (*right > elem) {
--right;
if (right == left)
return right;
}
// Если итераторы не совпали, значения итераторов меняются и цикл продолжается
if (left != right) {
std::swap(*left, *right);
++left;
}
}
return left;
}
void quicksort(std::vector<int>::iterator left, std::vector<int>::iterator right) {
if (left >= right) {
return;
}
// Выбираю рандомный элемент из массива
auto elem = rand() % (right - left) + left;
// Соответственно опорный элемент, относительно которого массив будет делиться на части
std::vector<int>::iterator pivot = partition(left, right, *elem);
// Рекурсивные вызовы. Возможно, проблему можно исправить здесь, делая
// std::swap(elem, pivot) и quickosort(left, pivot). То есть элемент,
// относительно которого все раскидалось будет в конце и массив поделиться относительно elem'a.
quicksort(left, pivot - 1);
quicksort(pivot + 1, right);
}
int main() {
size_t N = 0;
std::cin >> N;
std::vector<int> array(N);
for (size_t i = 0; i != N; ++i) {
std::cin >> array[i];
}
if (N != 0)
quicksort(array.begin(), array.end() - 1);
for (auto elem : array) {
std::cout << elem << " ";
}
}
Например:
7
7 7 7 -1 3 -1 -1 -> -1 -1 -1 7 3 7 7 (не понимаю, почему 3 оказалась именно там)
Или
6
-4 2 3 1 4 3 -> -4 1 3 2 3 4
partition()
послеswap
добавьте еще и--right
. / А для эффективности (как мне кажется) можно еще перед вызовом partition поменять случайный elem со средним в массиве.!=
-- обычно там пишутwhilе (left <= right)
. Да и циклы, в которых сдвигают left и right, стараются делать максимально короткими. Впрочем, лучше посто посмотрите нормальное (например, как у Кнута) описание алгоритма с его анализом, как правильно выбирать pivot и в каком порядке сортировать подмассивы после выбора pivot и почему тут лучше делать итерацию, а не рекурсию и т.д. и т.п.quicksort(pivot + 1, right);
тоже ошибка. Нужноquicksort(pivot, right);
.left == right
вpartiton()
надо возвращать left + 1 / И еще момент, вот тутauto elem = rand() % (right - left) + left;
выбирается elem из отрезка без последнего элемента. left -- первый, right -- последний, значит количество элементов = right - left + 1