Comparator Function

A comparator function is used to define custom comparison logic for ordering elements in a specific way. It allows flexible sorting based on arbitrary criteria rather than default comparison.

A comparator takes two elements as input, compares them, and returns a negative/zero/positive value if the first element is less than, equal to or greater than the second element respectively.

This return value controls how the elements are sorted by algorithms that accept a comparator.

Solution

Here is an example comparator function that sorts integers in descending order:

Java

1
2
3
4
5
6
7
8
9

import java.util.Comparator;

class DescendingComparator implements Comparator<Integer> {

  public int compare(Integer a, Integer b) {
    return b - a;
  }

}

C++

1
2
3
4
5
6
7
8
9

#include <functional>

struct DescendingComparator {

  int compare(int a, int b) {
    return b - a;
  }

};

Python

1
2
3
4
5
6
7

def descending_compare(a, b):
  if b > a:
    return -1
  elif b < a: 
    return 1
  else:
    return 0

We subtract parameters and flip signs to reverse default ordering.

Comparators provide flexible sorting based on custom logic.

Description: Comparator Function

A Comparator Function is a custom function used for sorting or comparing elements in a data structure based on certain criteria. It takes two arguments and returns a value indicating the relative order of those arguments. In most languages, a negative, zero, or positive value implies less than, equal to, or greater than, respectively.

Solution

Below are implementations demonstrating the use of comparator functions in Java, C++, and Python.

Java

In Java, the Comparator interface is used to create custom sorting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        Integer[] arr = {3, 1, 4, 1, 5, 9};
        
        // Using anonymous class
        Arrays.sort(arr, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });

        // Using lambda (Java 8+)
        Arrays.sort(arr, (a, b) -> b - a);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

C++

In C++, the sort function from <algorithm> can be customized using a comparator function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <algorithm>
#include <vector>

bool compare(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9};
    std::sort(vec.begin(), vec.end(), compare);

    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Python

In Python, the sorted function or sort method can use a custom comparator function through the key argument.

1
2
3
4
5
6
7
8
9

def compare(a):
    return a % 2

arr = [3, 1, 4, 1, 5, 9]
arr.sort(key=compare)

for num in arr:
    print(num, end=" ")
print()

Key Takeaways

• Comparator functions allow customization of the sorting algorithm.
• Java’s Comparator interface, C++’s sort function, and Python’s sorted function all support custom comparators.
• The comparator function should return a negative, zero, or positive integer to indicate relative ordering.
• Lambda expressions and anonymous classes (Java) can simplify the implementation.