отладка быстрой сортировки

Question

Может кто-нибудь указать, почему эта реализация быстрой сортировки не работает, я прошел через нее несколько раз и, похоже, не могу найти ошибку

int quickPartition ( int data[], int p, int r)
{
    int x=data[r];
    int i=p-1;
    for (int j=p; j<r; j++)
    {
        if(data[j]<x)
        {
            i++;
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        int temp=data[i+1];
        data[i+1]=data[r];
        data[r]=temp;   
    }
    i++;
    cout<<"i:"<<i<<endl;
    return i;
}

void myQuickSort(int data[], int left, int right)
{       
    if(left<right)
    {
        int q=quickPartition(data,left,right);
        myQuickSort(data,left,q-1);
        myQuickSort(data,q+1,right);
    }
}

вызов быстрой сортировки просто

myQuickSort(anArray,0,size-1);

Answer 1

Метинкс

    int temp=data[i+1];
    data[i+1]=data[r];
    data[r]=temp;

должны выходить за рамки for.

Answer 2

Ваша реализация раздела выглядит полностью поддельной. То, что вы хотите, это итерация с обоих концов и на каждом конце найти объект, который принадлежит противоположной части. Если итераторы встретятся, все готово. В противном случае вы меняете два объекта и находите следующую пару.

Лично я не могу правильно мыслить в тех абстракциях, которые вы используете: мне гораздо удобнее думать итераторами, указывающими на соответствующие объекты, и нахождение следующего объекта для свопинга также должно быть функциями. Кроме того, мне нужно разбить вещи на маленькие, понятные кусочки. Вы меняете объекты в какой-то момент. Это должно быть отдельной функцией. С этим разделом () будет выглядеть примерно так:

int* partition(int* left, int* right, int value) {
    while (left != right)
    {
         left = find_forward(left, right, value);
         right = find_backward(left, right, value);
         if (left != right)
         {
             swap(left, right);
         }
    }
    return left;
}

Я не проверял это, но что-то в этом роде должно работать. Очевидно, я бы просто использовал std::swap() для замены элементов и std::find_if() для поиска подходящих мест (для обратного случая с использованием std::reverse_iterator). Ну, если бы это было не домашнее задание, вы бы просто использовали std::sort() в любом случае: он не использует быструю сортировку ванили, а вариант, который обнаруживает, что он работает в плохом случае, и использует std::heap_sort() в этом случае чтобы гарантировать, что он остается O (n log n).