sort cmp function

general
1

can any one tell me how to use sort cmp for sorting a pair of values based on first if on tie based on second

2

If you need to sort based on first (second only if there is tie), use implicit sort function of c++ in algorithm.h header. Use a vector of pair and put values in the vector. Then sort the vector. The work is done in O(nlogn) time using quick sort.

You can also store first and second in two arrays. Sort first, whenever you require to make a swap, also swap the corresponding values in second array. If two elements are equal in first array, check the second array and make the swap there. If swap was required, also swap the corresponding elements in first.

I personally prefer the first one as built-in functions make the work easier, error free and efficient.

I personally use bubble sort for second approach. I have never tried it with a quick sort, but I think it can be done easily.

3

Hello, here is a simple example of the cmp function;
suppose we work with the Point structure, we firstly create the structure

struct Point {
   int x;
   int y;
   Point(int _x, int _y) : x(_x) , y(_y) {}
};

And then we create the function that compares two points

bool cmp(const Point &p1, const Point &p2){
    if(p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}

And then, we can sort a list of points easly;

vector<Point> v;
v.push_back(Point(5, 6));
v.push_back(Point(5, 4));
v.push_back(Point(2, 6));

sort(v.begin(), v.end(), cmp);

for(int i=0; i < v.size(); i++){
    cout << "(" << v[i].x << "," << v[i].y << ") ";
}

This should output the result :

(2,6) (5,4) (5,6)

Because we try to sort by x-axis and if tie by y-axis.

(Don’t forget to include vector and algorithm libraries)

2 Likes
4

Well, can anyone tell me how does the cmp function actually work, i.e., why do we have to create a struct and then create the cmp function with parameters

5

thanku i really liked ur post