3
class Foo
{
    public:
        int num;
        int other;
};

int main()
{
    Foo bar[10].num = {1, 9, 3, 5, 1, 6, 10, 0, 6, 3};

    //quicksort(bar)

    return 0;
}

I want to write a quicksort function that orders the 'bar' array by 'num' ascending. Not quite sure what is the best approach to take as I have never written a quicksort. I looked at some example codes, but I can't see how to modify them for this case. An inplace sort done by passing pointers to the first and last elements of the array doesn't work as this only sorts the 'num' member, not the whole object. Splitting the array of objects into a lower array, a pivot and a upper array and recursively sorting each looks promising, but I'm not sure how passing the values would work...

Any help greatly appreciated. Sorry if this has been asked before.

2
  • possible duplicate of c++ sort with structs
    – moinudin
    Jan 2, 2011 at 18:25
  • +1 i think it is quite a question like "what if i have something more complex than an array of values"? So it can be useful to start thinking about what is exactly a sorting function, and what is a compare function in particular. How can distance between complex elements to be measured? Feb 7, 2011 at 9:44

4 Answers 4

11

First you write a function(or functor) to compare your objects by whatever value you want. It should take two objects and return a bool. It should return true if the first should come before the second, false otherwise. Then pass that to the std::sort.

struct compare_Foo_by_num
{
    bool operator() (const Foo & lhs, const Foo & rhs) { return lhs.num < rhs.num; }
};

int main()
{
    Foo bar[10];

    std::sort(bar, bar+10, compare_Foo_by_num());
}
3
  • The comparator must also return false on equal values, i.e. it should act like a < operator.
    – moinudin
    Jan 2, 2011 at 18:24
  • This works great, thanks! I'll have to look into how the std::sort works if I decide to write my own, but this is good for what I am writing.
    – Rich
    Jan 2, 2011 at 18:30
  • 2
    @Rich: writing your own quicksort is a bad idea, except for educational purposes
    – Roman L
    Jan 2, 2011 at 18:42
3

You can overload operator< to compare the desired member and then use std::sort.

#include <algorithm>

class Foo
{
public:
    int num;
    int other;
};

bool operator<(const Foo& x, const Foo& y)
{
    return x.num < y.num;
}

int main()
{
    Foo bar[10] = {{1, 5}, {9, 2}, {3, 0}, {5, 7}, {1, 3}, {6, 4}, {10, 8}, {0, 9}, {6, 2}, {3, 5}};
    std::sort(bar + 0, bar + 10);
}

Note that you need two numbers to initialize a Foo, not just the one you are interested in when sorting.

If you cannot or do not want to overload operator< for Foo, other options include passing a good old C style function pointer or a C++ style function object as a third parameter to std::sort.

1

Another alternative is to use std::sort with a lambda expression:

int main()
{
    Foo bar[10] = {{1,5},{9,2},{3,0},{5,7},{1,3},{6,4},{10,8},{0,9},{6,2},{3,5}};

    std::sort(bar, bar + 10, [](const Foo &x, const Foo &y) {
        return x.num < y.num;
    });
}
0

If you adamant on implementing your your own quicksort, I suggest watching this video to help you better visualize the algorithm. Though you've never written a quicksort you may find it easier to implement after watching it. http://www.youtube.com/watch?v=vxENKlcs2Tw

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.