C++

Forum

 
Sorting Classes using Merge Sort

yonifra (8)
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 (310)
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 (8)
Thanks a lot! You really helped a lot!
Topic archived. No new replies allowed.