Extensible Sorting with Custom Comparators

mgcadmin 19-10-2021

Extensible Sorting

You may have encountered this situation before: You have a collection of objects that need sorting, but you want to be able to sort the objects differently depending upon which value or values you use to sort them. In this situation operator overloading is the wrong the tool for the job.

What we need, is custom comparators. Custom Comparators are functions used in place of C++'s built in Logical operators, in this way we can use standard sorting algorithms to sort non-standard types in such a way that neither templates nor operator overloading could accomplish.

Custom Comparators

Suppose we had an object type "student" had data fields for Name, Grade level, Birthday, and GPA and we want to be able to sort the objects according to any of these fields.

struct Student {
    std::string name;
    int age;
    int grade_level;
    double gpa;
};

 

Implementing a series of methods for the different data fields is trivial:

bool nameCmp(Student *lhs, Student *rhs)
{
   return lhs->name < rhs->name;
}

bool ageCmp(Student *lhs, Student *rhs)
{
   return lhs->age < rhs->age;
}

bool grade_levelCmp(Student *lhs, Student *rhs)
{
  return lhs->grade_level < rhs->grade_level;
}

bool gpaCmp(Student *lhs, Student *rhs)
{
  return lhs->gpa < rhs->gpa;
}

 

So now that we have our custom comparators how to can we use them in one sorting function without having to write a different sorting function for each custom comparator, which is what we were trying to avoid to being with? The answer is function pointers.

Function Pointers

C++ inherited function pointers from C, and they're an elegant solution with an ugly syntax to the question of passing functions as parameters to other functions. While the syntax leaves something to be desired, they add another level of extensibility to our functions that is crucial for writing complex programs, and while the example at hand isn't that exciting, it opens the doors.

Part of what makes the syntax of function pointers so ugly is that we need to make use of operator/pointer preference so the compiler knows that it is a pointer to a function that we are passing. To get a better Idea, lets take a look at the sorting function we are using to sort our records (pay attention to the parts in bold):

template <typename T>

void selectionSort(T arr[], int n, bool (*cmp)(T,T))
{
   for (int i = 0; i < n; i++)
   {
     int l = i;
     for (int j = i; j < n; j++)
     {
       if (cmp(arr[j], arr[l]))
       {
         l = j;
       }
     }
     swap(arr, i, l);
   }
}

 

It's a standard selection sort that we have templated so that we can pass it an array of any type. Whats of particular interest to us is the third function parameter.

This funky looking thing:

bool (*cmp)(T,T)

Thats the syntax for declaring a function pointer as a parameter. In our case its a function that returns a bool type, and accepts at its arguments, to instances of the templated type T.

 

Putting it together

Now that we have our pieces in place, lets use the following program to sort our data according to our preferences:

Compiling and running the above program will yield us the following output:

Sorted By Name:
-------------------
 Name: Adam
  Age: 21
Grade: 15
  GPA: 2.75
-----------------
 Name: Jessica
  Age: 22
Grade: 16
  GPA: 3.75
-----------------
 Name: Lola
  Age: 20
Grade: 15
  GPA: 3.4
-----------------
 Name: Max
  Age: 34
Grade: 16
  GPA: 3.5
-----------------
 Name: Stefani
  Age: 19
Grade: 14
  GPA: 4
-----------------
Sorted by GPA
----------------
 Name: Adam
  Age: 21
Grade: 15
  GPA: 2.75
-----------------
 Name: Lola
  Age: 20
Grade: 15
  GPA: 3.4
-----------------
 Name: Max
  Age: 34
Grade: 16
  GPA: 3.5
-----------------
 Name: Jessica
  Age: 22
Grade: 16
  GPA: 3.75
-----------------
 Name: Stefani
  Age: 19
Grade: 14
  GPA: 4
-----------------
Sorted by Grade level:
----------------------
 Name: Stefani
  Age: 19
Grade: 14
  GPA: 4
-----------------
 Name: Lola
  Age: 20
Grade: 15
  GPA: 3.4
-----------------
 Name: Adam
  Age: 21
Grade: 15
  GPA: 2.75
-----------------
 Name: Jessica
  Age: 22
Grade: 16
  GPA: 3.75
-----------------
 Name: Max
  Age: 34
Grade: 16
  GPA: 3.5
-----------------

As you can see, depending on which comparator we used, the data is sorted based on the data in that field. This yields a whole new area of extensibility and power to our programs, and this is just a taste of what can be done. we can also effect the order of the sort: ascending vs descending, even values first, etc, etc.

The options are only limited by your imagination, so go out and experiment!

---