Quicksort to sort an array of objects by a particular member C++

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 orde开发者_StackOverflow社区rs 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.

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

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.

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

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