Как реализовать быструю сортировку с использованием формата итератора?

Question

Я пытался реализовать этот код с итераторами в C ++.Он отлично работает, например, для std :: less <> () в качестве компаратора, но дает неверные результаты при использовании std :: большее <> ().Моя реализация неверна?

template <typename RandomIt, typename Compare>
void QuickSort(RandomIt first, RandomIt last, Compare compare)
{
    if (std::distance(first, last) <= 1) return;
    RandomIt bound = Partition(first, last, compare);
    QuickSort(first, bound);
    QuickSort(bound, last);
}

template <typename RandomIt, typename Compare>
RandomIt Partition(RandomIt first, RandomIt last, Compare compare)
{
    auto pivot = std::prev(last, 1);
    auto i = first;
    for (auto j = first; j != pivot; ++j)
        if (compare(*j, *pivot))
            std::swap(*i++, *j);
    std::swap(*i, *pivot);
    return i;
}

Редактировать:

Пример ввода, используя std::greater: 1, 2, 3 Ожидаемый: 3, 2, 1 Фактический: 1, 2, 3

Answer 1

Существует очевидная проблема, заключающаяся в том, что вы не передаете compare во внутренние Quicksort s, поэтому, вероятно, они возвращаются к вашему случаю по умолчанию.

QuickSort(first, bound, compare);
QuickSort(bound, last, compare);

Answer 2

Быстрая сортировка:

/*
Description : QuickSort in Iterator format
Created     : 2019/03/04 
Author      : Knight-金 (https://stackoverflow.com/users/3547485)
Link        : https://stackoverflow.com/a/54976413/3547485

Ref: http://www.cs.fsu.edu/~lacher/courses/COP4531/lectures/sorts/slide09.html
*/

template <typename RandomIt, typename Compare>
void QuickSort(RandomIt first, RandomIt last, Compare compare)
{
    if (std::distance(first, last)>1){
        RandomIt bound = Partition(first, last, compare);
        QuickSort(first, bound, compare);
        QuickSort(bound+1, last, compare);
    }
}

template <typename RandomIt, typename Compare>
RandomIt Partition(RandomIt first, RandomIt last, Compare compare)
{
    auto pivot = std::prev(last, 1);
    auto i = first;
    for (auto j = first; j != pivot; ++j){
        // bool format 
        if (compare(*j, *pivot)){
            std::swap(*i++, *j);
        }
    }
    std::swap(*i, *pivot);
    return i;
}

---

Тестовый код:

std::vector<int> vec = {0, 9, 7, 3, 2, 5, 6, 4, 1, 8};

// less 
QuickSort(std::begin(vec), std::end(vec), std::less<T>());

// greater 
QuickSort(std::begin(vec), std::end(vec), std::greater<int>());

---

Результат: