Mastering Comparators: A Beginner’s Guide to Custom Sorting

Introduction

Sorting and organizing data efficiently is a fundamental part of programming. But what if you need to sort elements in a custom order—say, sorting numbers in descending order, arranging objects based on a specific attribute, or prioritizing elements in a queue? This is where comparators in C++ come to the rescue!

Comparators are powerful tools that allow you to control how elements are compared and arranged. Whether you're working with basic data types, complex objects, or priority-based structures, comparators provide a flexible and efficient way to define custom sorting rules.

In this blog, we’ll break down comparators step by step with easy-to-understand explanations and practical C++ examples. By the end, you'll have a clear understanding of how to implement comparators in different scenarios and optimize your sorting logic.

Let’s dive in! 🚀

1. Basic Comparator (Sorting Integers in Descending Order)

Sorting numbers in descending order is one of the simplest examples of using a comparator.

Code:

#include <bits/stdc++.h>
using namespace std;

// Comparator function for descending order
bool compareDesc(int a, int b) {
    return a > b; // Return true if 'a' should come before 'b'
}

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};

    // Sort in descending order using the comparator
    sort(arr.begin(), arr.end(), compareDesc);

    // Print sorted array
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

Understanding the Code:

1. Comparator Function (compareDesc)
   • This function compares two numbers.
   • It returns true if the first number (a) is greater than the second (b).
   • This ensures larger numbers appear first in the sorted list.
2. Sorting the Vector

3. sort(arr.begin(), arr.end(), compareDesc);
   
   

   • The sort function uses compareDesc to sort numbers in descending order.
4. Printing the Sorted Array
   • The sorted list {9, 6, 5, 5, 2, 1} is printed.

Output:

9 6 5 5 2 1

2. Custom Object Comparator (Sorting Objects by Age in Ascending Order)

Sorting a list of objects requires a custom comparator based on a specific attribute. In this example, we sort people by age in ascending order.

Code:

#include <bits/stdc++.h>
using namespace std;

// Define a custom class
class Person {
public:
    string name;
    int age;

    Person(string n, int a) : name(n), age(a) {}
};

// Comparator to sort by age (ascending)
bool compareByAge(const Person &a, const Person &b) {
    return a.age < b.age; // Return true if 'a' should come before 'b'
}

int main() {
    vector<Person> people = {
        {"Gourab", 25},
        {"Deepak", 20},
        {"Rohit", 30}
    };

    // Sort by age using the comparator
    sort(people.begin(), people.end(), compareByAge);

    // Print sorted list
    for (const Person &p : people) {
        cout << p.name << " (" << p.age << ")\n";
    }
    return 0;
}

Understanding the Code:

1. Creating a Class (Person)
   • We define a class Person with name and age attributes.
   • A constructor initializes the values when an object is created.
2. Comparator Function (compareByAge)
   • Takes two Person objects and compares their ages.
   • Returns true if the first person is younger than the second.
   • This ensures sorting in ascending order of age.
3. Sorting the Vector

4. sort(people.begin(), people.end(), compareByAge);
   
   

   • Sorts the people vector based on the age attribute.
5. Printing the Sorted List
   • The sorted list {Deepak (20), Gourab (25), Rohit (30)} is printed.

Output:

Deepak (20)
Gourab (25)
Rohit (30)

3. Lambda Comparator (Sorting Integers in Ascending Order)

Instead of writing a separate function, lambda functions allow defining comparators inline.

Code:

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};

    // Sort in ascending order using a lambda function
    sort(arr.begin(), arr.end(), [](int a, int b) {
        return a < b; // Return true if 'a' should come before 'b'
    });

    // Print sorted array
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

Understanding the Code:

1. Lambda Function

2. [](int a, int b) { return a < b; }
   
   

   • A short, inline comparator that compares two numbers.
   • Returns true if a is smaller than b, ensuring ascending order.
3. Sorting the Vector

4. sort(arr.begin(), arr.end(), [](int a, int b) { return a < b; });
   
   

   • This sorts the array in ascending order.
5. Printing the Sorted Array
   • The sorted list {1, 2, 5, 5, 6, 9} is printed.

Output:

1 2 5 5 6 9

4. Priority Queue Comparator (Min-Heap Using Custom Comparator)

In priority queues, elements are processed in a specific order (e.g., highest or lowest priority first). A custom comparator is needed to create a min-heap, where the smallest element is always on top.

Code:

#include <bits/stdc++.h>
using namespace std;

// Comparator for min-heap (smallest element at the top)
class CompareMinHeap {
public:
    bool operator()(int a, int b) {
        return a > b; // Return true if 'a' should come before 'b'
    }
};

int main() {
    // Create a min-heap using the comparator
    priority_queue<int, vector<int>, CompareMinHeap> minHeap;

    // Insert elements
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);

    // Print elements in ascending order
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    return 0;
}

Understanding the Code:

1. Custom Comparator (CompareMinHeap)
   • Defines a functor (function object).
   • Overloads operator() and returns true if a > b, creating a min-heap.
2. Creating the Min-Heap

3. priority_queue<int, vector<int>, CompareMinHeap> minHeap;
   
   

   • Ensures the smallest element is always at the top.
4. Printing Elements in Ascending Order
   • The smallest element is always removed first.

Output:

5 10 20

Conclusion

Comparators give you complete control over sorting and ordering in C++. Whether you need custom sorting for objects, inline lambda comparators, or priority queue custom ordering, comparators help organize data efficiently.

Now that you understand how to implement and use comparators, go ahead and apply them in your projects! 🚀