Generic QuickSort implemented with vector and iterators C++

Question

I tried to write a generic quicksort using iterators but when I compiled it I got this error:

"In instantiation of ‘void QuickSortRec(std::vector, Iter, Iter) [with T = int; Iter = __gnu_cxx::__normal_iterator >]’: Iterators.cpp:49:53: required from here Iterators.cpp:133:28: error: no match for ‘operator/’ (operand types are ‘__gnu_cxx::__normal_iterator >’ and ‘int’) Iter pivot(_begin + (_end / 2));"

This is my code:

template<typename T, typename Iter>
void QuickSortRec(std::vector<T> _vector, Iter _begin, Iter _end)
{
    Iter pivot(_begin + (_end / 2));
    Iter left(_begin);
    Iter right(_end);

    while (left <= right)
    {
        while (*left < *pivot)
        {
            ++left;
        }

        while (*right > *pivot)
        {
            --right;
        }

        if (*left >= *right)
        {
            Swap(left, right);
            ++left;
            --right;
        }
    }

    if (_begin < right)
    {
        QuickSortRec(_vector, _begin, right);
    }

    if (left < _end)
    {
        QuickSortRec(_vector, left, _end);
    }
}

template<typename Iter>
void Swap(Iter _a, Iter _b)
{
    Iter temp(_b);
    *_b = *_a;
    *_a = *temp;
}

Why do you pass a copy (!) of the vector on every recursion? You don't even use it for anything. — nwp, Dec 11 '18 at 10:22
what is `_begin + (_end / 2)` supposed to mean? You want the pivot half distance between begin and end? Thats not what this is expressions says. Its more like "divide end by 2 and then add it to begin" what should it mean to divide an iterator by 2? — 463035818_is_not_an_ai, Dec 11 '18 at 10:23
Of course you use partitioning, otherwise it's not quicksort. The partitioning is your first loop. You're not "splitting" the vector, and it's not something that quicksort does. — molbdnilo, Dec 11 '18 at 10:34
Your `Swap` is also broken, by the way. Write a non-template quicksort that takes two pointers first, then generalise. It looks like you started with a function that takes an array and two indices, which is not a good starting point. — molbdnilo, Dec 11 '18 at 10:36
To fix your compile error change `_end / 2` to `(_end - _begin) / 2`. You can't divide a RandomAccessIterator but you can divide the difference of two iterators — Thomas Sablik, Dec 11 '18 at 10:38
You may want to look [at this answer](https://stackoverflow.com/a/24650627/2610810) — Caleth, Dec 11 '18 at 13:33
That should be `if (left >= right)`, comparing the iterators, not the values. There are other issues. Normally quick sort uses first and last instead of begin and end, where last = --end. You'll need to adjust the code to deal with this. — rcgldr, Dec 11 '18 at 17:43
A key issue is that standard quicksort partition uses a pivot value, but in this case, the code is using a pivot iterator, and if the pivot is swapped, this changes the pivot value in the middle of a partition step, which messes up the quicksort algorithm. The algorithm will need to be modified to handle this case. — rcgldr, Dec 11 '18 at 19:52

rcgldr · Accepted Answer · 2018-12-12T05:29:44.220

Example of a Hoare partition type quicksort. Normally Hoare inits indexes to -1 and size, but the iterator equivalent of -1 is not allowed, so the first instance uses the equivalent of 0 and size-1, before falling into the main loop.

template <typename I>
void QuickSort(I beg, I end)
{
    if (end - beg < 2)
        return;
    I lft(beg);
    I rgt(end-1);
    auto pvt = *(lft + (rgt-lft)/2);
    if(*lft < pvt)
        while (*++lft < pvt) ;
    if(*rgt > pvt)
        while (*--rgt > pvt) ;
    while (lft < rgt)
    {
        std::iter_swap(lft, rgt);
        while (*++lft < pvt) ;
        while (*--rgt > pvt) ;
    }
    rgt++;
    QuickSort(beg, rgt);
    QuickSort(rgt, end);
}

Generic QuickSort implemented with vector and iterators C++

1 Answers1