How to implement quicksort using iterator format?

Question

I tried to implement this code with iterators in C++. It works fine for e.g. std::less<>() as comparator but gives incorrect results when using std::greater<>(). Is my implementation wrong?

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;
}

Edit:

Example input, using std::greater: 1, 2, 3 Expected: 3, 2, 1 Actual: 1, 2, 3

gives incorrect results, Is my implementation wrong? Well, is the algorithm supposed to give incorrect results? — eerorika
– eerorika, Commented Mar 3, 2019 at 23:11
Well, even a quick glance shows differences between your implementation and the code you copied. QuickSort(bound, last); should be QuickSort(bound + 1, last); for instance. — john
– john, Commented Mar 3, 2019 at 23:14
The referenced algorithm uses also a less-than/eqal-as operator. This may be important. — MiCo
– MiCo, Commented Mar 3, 2019 at 23:38
Related to the stack overflow: stackoverflow.com/questions/33452614/… — tevemadar
– tevemadar, Commented Mar 3, 2019 at 23:42

Kinght 金 · Accepted Answer · 2019-03-04 08:59:06Z

4

QuickSort:

/*
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;
}

Test code:

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>());

Result:

edited Mar 4, 2019 at 8:59

answered Mar 4, 2019 at 3:56

Kinght 金

18.4k5 gold badges63 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ava Over a year ago

Using compare(*j, *pivot)<=0 gives opposite results than expected. I wanted Compare to be comparator like in std::sort, returning boolean value. Removing the <=0 part solves the problem.

Caleth · Accepted Answer · 2019-03-04 10:06:32Z

2

There's the obvious problem that you aren't passing the compare to the inner Quicksorts, so presumably they are falling back to your default case.

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

answered Mar 4, 2019 at 10:06

Caleth

66k2 gold badges53 silver badges101 bronze badges

Collectives™ on Stack Overflow

How to implement quicksort using iterator format?

2 Answers 2

QuickSort:

Test code:

Result:

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

QuickSort:

Test code:

Result:

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related