Sorting Classes using Merge Sort

Hi all,

I'm very new to C++ but not so new to programming (I know C language and HTML)
Well, what I wanted to ask is how do I implement a sorting mechanism using the famous Merge Sort algorithm to sort various parameters of a class (Say, I have a class named Car with parameters: Color, Type, Model and I want to sort first by type, then model, then by color)

I would appreciate an insightful answer :)

Thanks!

Jonathan.

ropez (312)

All you need to do is implement a function to compare two objects of the class. For this, you would normally use either the less than operator, '<', or a "functor".

Operator:

1 2 3 4 5 6 7 8 9 10

bool operator<(const Car & a, const Car & b) {
  if (a.type != b.type)
    return a.type < b.type;
  if (a.model != b.model)
    return a.model < b.model;
  if (a.color != b.color)
    return a.color < b.color;
  
  return false; // They are equal
}

Functor:

1 2 3 4 5 6

class CarLessThan {
  public:
    bool operator()(const Car & a, const Car & b) {
      // Same code as above
    }
};

Using these, you can sort a collection of Car objects using sort functions in the standard library:

1 2 3 4 5 6 7 8 9

std::vector<Car> cars;
// Add objects to list

// Using less than operator:
std::sort(cars.begin(), cars.end());

// Using functor:
CarLessThan clt;
std::sort(cars.begin(), cars.end(), clt);

If you want to manually implement the sort algorithm, you can compare two objects like this:

1 2 3 4 5 6 7 8 9

if (car1 < car2) {
  // Do something
}

// or

if (clt(car1, car2) {
  // Do something
}

There are other standard library functions that you might be interested in:
http://www.cplusplus.com/reference/algorithm/merge.html
http://www.cplusplus.com/reference/algorithm/swap.html

And many others. Good luck.

yonifra (6)

Thanks a lot! You really helped a lot!

This topic is archived - New replies not allowed.


		C++ : Forums : Beginners : Sorting Classes using Merge Sort Search: