Sort algorithm which sorts objects by data inside using templates

Question

I have an assignment to create a code which uses templates.

Seemingly, one of the easiest ways to use them in my code would be to implement a sorting algorithm that sorts an array of objects based on different values stored inside them. Is it even possible to implement templates like that? Will it make any sense to do so?

Here is what my class should look like:

class Data{
    private:
        int x;
        double y;
    public:
        void setX(int a){x = a;};
        void setY(double a){y = a;};
        int getX(){return x;};
        double getY(){return y;};
};

int main(){
    Data A[10];
    return 0;
}

I need to make a sorting algorithm which could sort this array by Data::x and by Data::y. The speed of algorithm does not matter, it can be a simple bubble sort.

Answer 1

EDIT: Now that I have reread(and edited) your question, it seems you have tasked yourself with implementing a dumbed down version of one of the overloads of std::sort. Note that if you are just required to use templates in any way possible, making a class template would be much easier. The rest of this answer was written as if your professor had explicitly asked you to implement such a sorting algorithm.

I think the point of your assignment is to get you to understand the use of custom comparison functions(also known as predicates or comparators) in sorting algorithms. You pass in one function for comparing based on Data::x_ and another for comparing based on Data::y_.

Here is an example:

class Data
{
public:
    Data(int x, double y)
        : y_(y), x_(x)
    {}

    void setX(int x) { x_ = x; }
    void setY(double y) { y_ = y; }
    int getX() const { return x_; }
    double getY() const { return y_; }

private:
    double y_;
    int x_;
};

template <typename RandomIt_, typename Compare_>
void data_sort(RandomIt_ first, RandomIt_ last, Compare_ cmp)
{
    for (auto i = first; i != last; ++i)
        for (auto j = i+1; j != last; ++j)
            if (!cmp(*i, *j))
                std::swap(*i, *j);
}

void print_data(Data* d, size_t n)
{
    for (int i = 0; i < (int)n; i++)
        printf("Data: x: %d, y: %f\n", d[i].getX(), d[i].getY());
}

int main()
{
    Data a[5] = { Data(0, 4), Data(1, 3), Data(2, 2), Data(3, 1), Data(4, 0) };

    printf("Sorting based on ints:\n");
    data_sort(&a[0], &a[5], [](const Data& lhs, const Data& rhs) {
        return lhs.getX() < rhs.getX();
    });

    print_data(&a[0], 5);
    printf("\n");

    printf("Sorting based on doubles:\n");
    data_sort(&a[0], &a[5], [](const Data& lhs, const Data& rhs) {
        return lhs.getY() < rhs.getY();
    });

    print_data(&a[0], 5);
    return 0;

The sorting function is admittedly crap, but you should get the idea. If you aren't allowed to use C++11 for some reason, you can manually define functors like this:

struct IntCompare
{
    bool operator()(const Data& lhs, const Data& rhs)
    {
        return lhs.getX() < rhs.getX();
    }
};

struct DoubleCompare
{
    bool operator()(const Data& lhs, const Data& rhs)
    {
        return lhs.getY() < rhs.getY();
    }
};

and use them like this:

data_sort(&a[0], &a[5], IntCompare());
data_sort(&a[0], &a[5], DoubleCompare());

You would also have to get rid of the autos.

Note that if you are doing this outside of an assignment, you should probably use std::sort, as it is structured exactly the same way(except with a much better implementation). e.g.

 std::sort(&a[0], &a[5], IntCompare());
 std::sort(&a[0], &a[5], DoubleCompare());

The output of the example is:

Sorting based on ints:
Data: x: 0, y: 4.000000
Data: x: 1, y: 3.000000
Data: x: 2, y: 2.000000
Data: x: 3, y: 1.000000
Data: x: 4, y: 0.000000

Sorting based on doubles:
Data: x: 4, y: 0.000000
Data: x: 3, y: 1.000000
Data: x: 2, y: 2.000000
Data: x: 1, y: 3.000000
Data: x: 0, y: 4.000000