How to Set Up Comparator for QuickSort

Question

I'm having issues with comparators in C++. Right now, I'm simply trying to implement quicksort in Goodrich's book Data Structures and Algorithms in C++ with generic parameters. Here is the code from the book:

#include <iostream>
#include <vector>
#include <functional>

template <typename E, typename C> // quick-sort S void quickSort(std::vector<E>& S, const C& less) {
void quickSort(std::vector<E>& S, const C& less){
        if (S.size() <= 1)
            {return;}// already sorted
        quickSortStep(S, 0, S.size()-1, less); // call sort utility
}


template <typename E, typename C>
void quickSortStep(std::vector<E>& S, int a, int b, const C& less) {
    if (a >= b) {return;}
    E pivot = S[b];
    int l=a;
    int r=b-1;
    while (l <= r) {
        while (l <= r && !less(pivot, S[l]))
            {l++;}//pivot is greater than S[l]
        while (r >= l && !less(S[r], pivot))
            {r--;}
        if (l < r)
            {std::swap(S[l], S[r]); std::swap(S[l], S[b]);}
        quickSortStep(S, a, l-1, less);
        quickSortStep(S, l+1, b, less);
    }
}

I found code for a template that would compare ints and doubles and am trying to make it work for this program. However, when I pass in the function isLess as a parameter and try to run the program I get a build error: Call to function 'quickSortStep' that is neither visible in the template definition nor found by argument-dependent lookup. I have pasted the code for the isLess function below as well as my main and would appreciate any suggestions on how to implement a comparator probably.

template <typename T>
bool isLess(T a, T b)
{
    return a<b;
}


int main(int argc, const char * argv[]) {
    //vector and comparator
    int myInts[]={15,2,7,99};
    std::vector<int>myVec(myInts,myInts+sizeof(myInts)/sizeof(int));
    int a,b;
    quickSort(myVec,isLess<int>(a, b));
    return 0;
}

EDIT::

the book's code didn't sort correctly, so I made the following adjustments to quickSortStep() and it works fine now:

void quickSortStep(std::vector<E>& S, int a, int b, const C& less) {
    if (a >= b) {return;}
    E pivot = S[b];
    int l=a;
    int r=b-1;
    while (l <= r) {
        while (l <= r && !less(pivot, S[l]))
            {l++;}//pivot is greater than S[l]
        while (r >= l && !less(S[r], pivot))
            {r--;}
        if (l < r)
            {
                std::swap(S[l], S[r]);

            }
    }
    std::swap(S[l], S[b]);
    quickSortStep(S, a, l-1, less);
    quickSortStep(S, l+1, b, less);
}

*I found code for a template* -- [You should have searched here](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Mar 24 '18 at 00:59
*with generic parameters* -- Those parameters are not really generic. What if you wanted to sort a `std::deque`, or a regular array using your function? It is hard-coded to sort only vectors. It should be using iterators, as the link in my first comment shows. — PaulMcKenzie, Mar 24 '18 at 01:20

Jive Dadson · Accepted Answer · 2018-03-24T01:08:08.780

0

The code below answers your question. But the quicksort does not work. Maybe you transcribed it incorrectly.

template <typename T>
bool isLess(T a, T b)
{
    return a<b;
}


int main(int argc, const char * argv[]) {
    //vector and comparator
    std::vector<int> myVec { 15,2,7,99 };
    quickSort(myVec,isLess<int>);
    auto OK = std::is_sorted(myVec.begin(), myVec.end());
    assert(OK);
    return 0;
}

edited Mar 24 '18 at 01:08

answered Mar 24 '18 at 01:00

Jive Dadson

16,680
9
52
65

2

I didn't down vote this, but your answer is essentially a code only answer with no explanation of why the OP's code doesn't compile, or why the changes you made fix the problem. – 1201ProgramAlarm Mar 24 '18 at 01:16
Thank you for solving my problem, I did transcribe it wrong, misplacing `std::swap(S[l], S[b]);` – I Like Mar 24 '18 at 01:22
This answer is basically "Here is your fixed code, don't mind the many changes I made". – miradulo Mar 24 '18 at 01:23

How to Set Up Comparator for QuickSort

1 Answers1