Использование вектора и рекурсия в быстрой сортировке

Question

Объясните, пожалуйста, почему в этом коде быстрой сортировки:

#include <bits/stdc++.h>
using namespace std;
void QuickSort(vector<int>& in, int left, int right)
{
    if(right - left == 1)
    {
        return;
    }
    int x = in[rand() % in.size()];
    int m = left;
    for(int i = 0; i < in.size(); i++)
    {
        if(in[i] < x)
        {
            swap(in[i], in[m]);
            m++;
        }
    }
    QuickSort(in, left, m);
    QuickSort(in, m + 1, right);
}
int main()
{
    vector<int> a = {5, 4, 3, 2, 1, 10, 8, 14, 7, 6, 11};
    int left = 0;
    int right = a.size() - 1;
    QuickSort(a, left, right);
    for(int x : a)
    {
        cout << x << ' ';
    }
}

в последний элемент вектора записывается какое-то рандомное отрицательное большое число, при том, что в первый элемент вектора записывается верное число - 5? В чем ошибка? Заранее спасибо.

Answer 1

Код подразумевает использование схемы разделения Ломуто (а не Хоара), однако реализация содержит некоторые проблемы:

-на подмассиве длиной 1 условие выхода не выполняется (оно для длины 2)
-выбор опоры и цикл проводится по всему массиву, а не по нужной части
-даже если это поправить, значение m не является правильным разделительным индексом, т.к. часто in[m] > x (pivot)

Рабочий вариант (ideone) со случайным выбором опорного элемента (pivot)

void QuickSort(vector<int>& in, int left, int right)
{
    if (right <= left)
        return;
    int ipi = left + rand() % (right - left + 1);
    swap(in[ipi], in[right]);
    int x = in[right];
    int m = left;
    for (int i = left; i < right; i++)
        if (in[i] <= x)
            swap(in[i], in[m++]);
    swap(in[m], in[right]);
    QuickSort(in, left, m);
    QuickSort(in, m + 1, right);
}

БЛОГ НА HUSL

Использование вектора и рекурсия в быстрой сортировке

Ответы (1 шт):