Custom comparator function | Cpp

4562

Previously I had struggled with the custom comparator function for sorting. As a result, I could not code my thoughts when solving Djikstra, priority queue or when the problem requires custom sorting. I failed, explored and learned.

This is what i learned, and wanted to share
-> custom sort in increasing or decreasing order
-> sorting on pairs
-> Min and Max Heap
-> ordering in Sets and priorityQueue for user defined data type
-> complex Sorting conditions

Level1 : custom sort in increasing or decreasing order

int32_t main()
{
    vector<int> arr = {7,8,9,1,2,6,4,3};

    auto cmpInc = [](int a, int b)
    {
        return a<b;
    };
    auto cmpDec = [](int a, int b)
    {
        return a>b;
    };

    sort(arr.begin() , arr.end() , cmpInc);     // sorts array in increasing order
    sort(arr.begin() , arr.end() , cmpDec);     // sorts array in decreasing order

    for(auto i : arr)
        cout<<i<<" ";
}

Level 2 : custom Sort on pairs

int32_t main()
{
    vector<pairs<int,int>> arr = {{1,2},{2,2},{8,6},{1,4},{8,2},{3,7},{8,4}};

    auto cmpFirst = [](pair<int,int> a, pair<int,int> b)
    {
        return a.first < b.first;
    };
    auto cmpSecond = [](pair<int,int> a, pair<int,int> b)
    {
        return a.second < b.second;
    }
    auto cmp_FirstInc_SecDec = [](pair<int,int> a, pair<int,int> b)
    {
        if(a.first != b.second)
            return a.first < b.first;
        return a.second > b.second;
    };

    sort(arr.begin() , arr.end() , cmpFirst );          // sorts on first 
    sort(arr.begin() , arr.end() , cmpSecond);          // sorts on second
    sort(arr.begin() , arr.end() , cmp_FirstInc_SecDec);// first sorts on first in Increasing order then sorts on second decreasing order
}

Level 3 : Min and Max Heap

int32_t main()
{
    vector<int> a = {7,8,9,1,2,6,4,3};

    auto cmpForMaxHeap = [](int a, int b)
    {
        return a < b;    // observe the condition carefully, this is reverse to what we have done for sorting array using inbuilt sort
    };
    auto cmpForMinHeap = [](int a, int b)
    {
        return a > b;
    };

    priority_queue<int,vector<int>, decltype(cmpForMaxHeap)> maxHeap(cmpForMaxHeap);
    priority_queue<int,vector<int>, decltype(cmpForMinHeap)> minHeap(cmpForMinHeap);

    for(auto i : a)
        minHeap.push(i),
        maxHeap.push(i);

    cout<<"Printing minHeap\n";
    while(minHeap.size())   cout<<minHeap.top()<<" ", minHeap.pop();

    cout<<"\nPrinting maxHeap\n";
    while(maxHeap.size())   cout<<maxHeap.top()<<" ", maxHeap.pop();
}

level 4 : ordering in Sets and priorityQueue for user defined data type
Level 5 : Complex sorting condition

Define a structure/class named Student, Attributes should be name, marks, rollNumber , enrollment Number;
    name             = name of student
    rollNumber       = roll number of student
    marks            = marks of student
    enrollmentNumber = unique number denoting when the student was enrolled in school
    
-> NOTE: Name rollNumber marks can be same ( two students from different section can have same roll and name)
       : enrollment number will not be given you can use a count(this refers to the unique number then the student first registered in school)
Question : Sort the student according to following rules

  first sort according to marks, stundent with greater marks should come first ( decending order)
  if marks are same then sort according to rollNumber in acending order
  if even marks are same then sort according to name, lexographically
  if even name are same then sort according to enrollment number acending order

  Sample :  name , marks , rollNumber
            "Rohan"   33    2
            "John"    87    11
            "Basu"    24    12
            "Chandu"  94    15
            "Daman"   81    19
            "Seema"   24    15
            "Daman"   81    19

						**OUTPUT**
 Chandu     rollNumber: 15   marks: 94       enrollmentNumber: 4
 John       rollNumber: 11   marks: 87       enrollmentNumber: 2
 Daman      rollNumber: 19   marks: 81       enrollmentNumber: 5
 Daman      rollNumber: 19   marks: 81       enrollmentNumber: 7
 Rohan      rollNumber: 2    marks: 33       enrollmentNumber: 1
 Basu       rollNumber: 12   marks: 24       enrollmentNumber: 3
 Seema      rollNumber: 15   marks: 24       enrollmentNumber: 6

Q1 : Try Solving using custom Sorting
Q2 : Try Solving using PriorityQueue
Q3 : Try Solving using Sets ( since enrollment numbers are gonna be unique )**

Try it on, if you were not able to code, dont worry you can explore this

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

static int _ct = 0;
struct Student
{
    string name;
    int marks, rollNumber, enrollmentNumber;
    Student(string _name, int _marks, int _rollNumber) : name(_name) , marks(_marks) , rollNumber(_rollNumber) , enrollmentNumber(++_ct){};
    void printStudent()
    {
        cout<<"Name "<<name<<"\t";
        printf("rollNumber: %d \t marks: %d \t enrollmentNumber: %d \n" , rollNumber , marks , enrollmentNumber);
    }
};

int32_t main()
{
    vector<Student> student ={
                        //       name , marks , roll
                        Student("Rohan" , 33 , 2),
                        Student("John" , 87 , 11),
                        Student("Basu" , 24 , 12),
                        Student("Chandu" , 94 , 15),
                        Student("Daman" , 81 , 19),
                        Student("Seema" , 24 , 15),
                        Student("Daman" , 81 , 19),
                        };
    vector<Student> studentList1 = student;
    vector<Student> studentList2 = student;
    vector<Student> studentList3 = student;

// Solution for 1st question
    auto cmp1 = [](const Student &a, const Student &b)
    {
        if(a.marks != b.marks)
            return a.marks > b.marks;
        else if(a.rollNumber != b.rollNumber)
            return a.rollNumber < b.rollNumber;
        else if (a.name != b.name)
            return a.name < b.name;
        else 
            return a.enrollmentNumber < b.enrollmentNumber;
    };

    sort(studentList1.begin() , studentList1.end() , cmp1);

    for(auto i : studentList1)
        i.printStudent();
    
    cout<<endl;

// solution for 2nd Question
    
    auto cmp2 = [](const Student &a, const Student &b)
    {
        if(a.marks != b.marks)
            return a.marks < b.marks;
        else if(a.rollNumber != b.rollNumber)
            return a.rollNumber > b.rollNumber;
        else if (a.name != b.name)
            return a.name > b.name;
        else 
            return a.enrollmentNumber > b.enrollmentNumber;
    };

    priority_queue<Student , vector<Student> , decltype(cmp2)> pq(cmp2);

    for(auto i : studentList2)
        pq.push(i);
    
    for(auto &i : studentList2)
        i = pq.top() , 
        pq.pop();
    
    for(auto i :studentList2)
        i.printStudent();

    cout<<endl;

// Solution 3  using sets , we can use sets beacause enrollment numbers are different

    set<Student , decltype(cmp1)> Set(cmp1);
    for(auto i:studentList3)
        Set.insert(i);

    for(auto i : Set)
        i.printStudent();
}