Не работает самописный алгоритм быстрой сортировки

Question

Не могу понять в чем ошибка(неправильно сортирует вектор). Подскажите, пожалуйста, что исправить.

template <typename iter, typename Comparator>
void QuickSort(iter begin, iter end, Comparator cmp)
{
    if (begin == end)
        return;

    iter left = begin;
    iter right = end - 1;
    iter pivot = left++;

    if (left >= right)
        return;

    while (left != right)
    {
        if (cmp(*left, *pivot))
        {
            left++;
        }
        else
        {
            while (left != right)
            {
                if (cmp(*right, *pivot))
                {
                    std::iter_swap(right, left);
                    break;
                }
                else
                    right--;
            }
        }
    }
    --left;
    std::iter_swap(left, pivot);
    QuickSort(pivot, left, cmp);
    QuickSort(right, end, cmp);
}

int main()
{
    std::vector<int> vect{ 10, 4, 1, 0, 64, 5, 14, 65 };
    QuickSort(vect.begin(), vect.end(), [](int a, int b) { return a < b; });
    for (auto x : vect)
    {
        std::cout << x << ' ';
    }

    return 0;
}

Answer 1

Не уверен, что нашел все ваши ошибки, но по крайней мере, ваш пример сортируется верно.

template <typename iter, typename Comparator>
void QuickSort(iter begin, iter end, Comparator cmp)
{
    if (begin == end)
        return;

    iter left = begin;
    iter right = end - 1;
    iter pivot = left;
    pivot++;

    if (left >= right)
        return;

    while (left < right)
    {
        while(cmp(*left, *pivot)) left++;
        while(cmp(*pivot,*right)) right--;
        if (left < right) std::iter_swap(right, left);
    }

    std::iter_swap(left, pivot);
    QuickSort(begin, left, cmp);
    QuickSort(right, end, cmp);
}

Answer 2

Спасибо всем, кто ответил. Я, наконец, написал рабочую версию функции быстрой сортировки.

template <typename iter, typename Comparator>
void QuickSort(iter begin, iter end, Comparator cmp)
{
    if (end - begin <= 1)
        return;

    iter left = begin + 1;
    iter right = end - 1;
    iter pivot = begin;

    while (left <= right)
    {
        if (cmp(*left, *pivot) || *left == *pivot)
            left++;
        else if (cmp(*pivot, *right) || *pivot == *right)
            right--;
        else
            std::iter_swap(left, right);
    }
    std::iter_swap(right, pivot);
    QuickSort(pivot, right, cmp);
    QuickSort(left, end, cmp);
}

БЛОГ НА HUSL

Не работает самописный алгоритм быстрой сортировки

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