### You're not signed in!

Somewhat Frequent
0/8

# Sorting with Custom Comparators

Authors: Darren Yao, Siyong Huang, Michael Cao, Benjamin Qi

### Prerequisites

If we use custom objects or if we want to sort elements in an order other than the default, then we'll need to define a custom comparator.

Resources
IUSACOpartially based off this
CPHshort overview of what this module will cover

## Example: Wormhole Sort

Focus Problem – read through this problem before continuing!

We won't discuss the full solution here, as some of the concepts necessary for solving this problem will be introduced later in Silver. However, many solutions to this problem start by sorting the edges in nondecreasing order of weight. For example, the sample contains the following edges:

1 2 9
1 3 7
2 3 10
2 4 3


After sorting, it should look like

2 4 3
1 3 7
1 2 9
2 3 10


With C++, the easiest method is to use a vector of nested pairs:

1#include <bits/stdc++.h>2using namespace std;3
4#define f first5#define s second6
7int main() {8    int M = 4;9    vector<pair<int,pair<int,int>>> v;10    for (int i = 0; i < M; ++i) {

or a vector of array<int,3>s or vector<int>s:

1int main() {2    int M = 4;3    vector<array<int,3>> v; // or vector<vector<int>>4    for (int i = 0; i < M; ++i) {5        int a,b,w; cin >> a >> b >> w;6        v.push_back({w,a,b});7    }8    sort(begin(v),end(v));9    for (auto e: v) cout << e[1] << " " << e[2] << " " << e[0] << "\n";10}

In Python, we can use a list of lists.

But in Java, we can't sort an ArrayList of ArrayLists without writing some additional code. What should we do?

• If we only stored the edge weights and sorted them, we would have a sorted list of edge weights, but it would be impossible to tell which weights corresponded to which edges.
• However, if we create a class representing the edges and define a custom comparator to sort them by weight, we can sort the edges in ascending order while also keeping track of their endpoints.

## Classes

First, we need to define a class that represents what we want to sort. In our example we will define a class Edge that contains the two endpoints of the edge and the weight.

C++

### C++

A C++ struct is the same as a class in C++, but all members are public by default.

1#include <bits/stdc++.h>2using namespace std;3
4struct Edge {5    int a,b,w;6};7
8/* alternatively,9class Edge {10    public:

Java

1import java.util.*;2
3public class Sol {4    static class Edge {5        int a,b,w;6        public Edge(int _a, int _b, int _w) { a = _a; b = _b; w = _w; }7    }8    public static void main(String[] args) {9        int M = 4;10        Scanner in = new Scanner(System.in);

Python

1class Edge:2    def __init__(self, a, b, w):3        self.a = a4        self.b = b5        self.w = w6
7v = []8M = 49for i in range(M):10    a,b,w = map(int,input().split())

## Comparators

Normally, sorting functions rely on moving objects with a lower value in front of objects with a higher value if sorting in ascending order, and vice versa if in descending order. This is done through comparing two objects at a time.

C++

What a comparator does is compare two objects as follows, based on our comparison criteria:

• If object $x$ is less than object $y$, return true
• If object $x$ is greater than or equal to object $y$, return false

Essentially, the comparator determines whether object $x$ belongs to the left of object $y$ in a sorted ordering. A comparator must return false for two identical objects (not doing so results in undefined behavior and potentially a runtime error).

In addition to returning the correct answer, comparators should also satisfy the following conditions:

• The function must be consistent with respect to reversing the order of the arguments: if $x \neq y$ and compare(x, y) is true, then compare(y, x) should be false and vice versa.
• The function must be transitive. If compare(x, y) is true and compare(y, z) is true, then compare(x, z) should also be true. If the first two compare functions both return false, the third must also return false.

This is the easiest to implement. However, it only works for objects (not primitives) and it doesn't allow you to define multiple ways to compare the same type of class.

In the context of Wormhole Sort (note the use of const Edge&):

1#include <bits/stdc++.h>2using namespace std;3
4struct Edge {5    int a,b,w;6    bool operator<(const Edge& y) { return w < y.w; }7};8
9int main() {10    int M = 4;

We can also overload the operator outside of the class:

1struct Edge {2    int a,b,w;3};4bool operator<(const Edge& x, const Edge& y) { return x.w < y.w; }

or within it using friend:

1struct Edge {2    int a,b,w;3    friend bool operator<(const Edge& x, const Edge& y) { return x.w < y.w; }4};

### Method 2: Comparison Function

This works for both objects and primitives, and you can declare many different comparators for the same object.

1#include <bits/stdc++.h>2using namespace std;3
4struct Edge {5    int a,b,w;6};7
8bool cmp(const Edge& x, const Edge& y) { return x.w < y.w; }9
10int main() {

We can also use lambda expressions in C++11 or above:

1sort(begin(v),end(v),[](const Edge& x, const Edge& y) { return x.w < y.w; });

Java

What a Comparator does is compare two objects as follows, based on our comparison criteria:

• If object $x$ is less than object $y$, return a negative integer.
• If object $x$ is greater than object $y$, return a positive integer.
• If object $x$ is equal to object $y$, return 0.

In addition to returning the correct number, comparators should also satisfy the following conditions:

• The function must be consistent with respect to reversing the order of the arguments: if compare(x, y) is positive, then compare(y, x) should be negative and vice versa.
• The function must be transitive. If compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0. Same applies if the compare functions return negative numbers.
• Equality must be consistent. If compare(x, y) = 0, then compare(x, z) and compare(y, z) must both be positive, both negative, or both zero. Note that they don't have to be equal, they just need to have the same sign.

Java has default functions for comparing int, long, double types. The Integer.compare(), Long.compare(), and Double.compare() functions take two arguments $x$ and $y$ and compare them as described above.

There are two ways of implementing this in Java: Comparable, and Comparator. They essentially serve the same purpose, but Comparable is generally easier and shorter to code. Comparable is a function implemented within the class containing the custom object, while Comparator is its own class.

### Method 1: Comparable

We'll need to put implements Comparable<Edge> into the heading of the class. Furthermore, we'll need to implement the compareTo method. Essentially, compareTo(x) is the compare function that we described above, with the object itself as the first argument, or compare(self, x).

When using Comparable, we can just call Arrays.sort(arr) or Collections.sort(list) on the array or list as usual.

1import java.util.*;2
3public class Sol {4    static class Edge implements Comparable<Edge> {5        int a,b,w;6        public Edge(int _a, int _b, int _w) { a = _a; b = _b; w = _w; }7        public int compareTo(Edge y) { return Integer.compare(w,y.w); }8    }9    public static void main(String[] args) {10        int M = 4;

### Method 2: Comparator

If instead we choose to use Comparator, we'll need to declare a second class that implements Comparator<Edge>:

1import java.util.*;2
3public class Sol {4    static class Edge {5        int a,b,w;6        public Edge(int _a, int _b, int _w) { a = _a; b = _b; w = _w; }7    }8    static class Comp implements Comparator<Edge> {9        public int compare(Edge a, Edge b) {10            return Integer.compare(a.w, b.w);

When using Comparator, the syntax for using the built-in sorting function requires a second argument: Arrays.sort(arr, new Comp()), or Collections.sort(list, new Comp()).

Python

### Defining Less Than Operator

1class Edge:2    def __init__(self, a, b, w):3        self.a = a4        self.b = b5        self.w = w6    def __lt__(self, y): # lt means less than7        return self.w < y.w8
9v = []10M = 4

### Key Function

This method maps an object to another comparable datatype with which to be sorted. In this case we map edges to their weights.

1class Edge:2    def __init__(self, a, b, w):3        self.a = a4        self.b = b5        self.w = w6
7v = []8M = 49for i in range(M):10    a,b,w = map(int,input().split())

### Comparison Function

A comparison function in Python must satisfy the same properties as a comparator in Java. Note that old-style cmp functions are no longer supported, so the comparison function must be converted into a key function with cmp_to_key.

1from functools import cmp_to_key2
3class Edge:4    def __init__(self, a, b, w):5        self.a = a6        self.b = b7        self.w = w8
9v = []10M = 4

## Variations

### Sorting in Decreasing Order of Weight

We can replace all occurrences of x.w < y.w with x.w > y.w in our C++ code. Similarly, we can replace all occurrences of Integer.compare(x, y) with -Integer.compare(x, y) in our Java code or negate the key in Python.

### Sorting by Two Criteria

Now, suppose we wanted to sort a list of Edges in ascending order, primarily by weight and secondarily by first vertex (a). We can do this quite similarly to how we handled sorting by one criterion earlier. What the comparator function needs to do is to compare the weights if the weights are not equal, and otherwise compare first vertices.

C++

1struct Edge {2    int a,b,w;3    bool operator<(const Edge& y) {4        if (w != y.w) return w < y.w;5        return a < y.a;6    }7};

Java

1static class Edge implements Comparable<Edge> {2    int a,b,w;3    public Edge(int _a, int _b, int _w) { a = _a; b = _b; w = _w; }4    public int compareTo(Edge y) {5        if (w != y.w) return Integer.compare(w,y.w);6        return Integer.compare(a,y.a);7    }8}

Python

1class Edge:2    def __init__(self, a, b, w):3        self.a = a4        self.b = b5        self.w = w6    def __lt__(self, y): # lt means less than7        return self.w < y.w if self.w != y.w else self.a < y.a

Sorting by an arbitrary number of criteria is done similarly.

C++

Java

With Java, we can implement a comparator for arrays of arbitrary length (although this might be more confusing than creating a separate class).

1import java.util.*;2
3public class Sol {4    static class Comp implements Comparator<int[]> {5        public int compare(int[] a, int[] b){6            for (int i = 0; i < a.length; ++i)7                if (a[i] != b[i]) return Integer.compare(a[i],b[i]);8            return 0;9        }10    }

Python

## Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
SilverEasy
SilverEasy
SilverNormalExternal Sol
GoldNormal
SilverHardExternal Sol
SilverVery HardExternal Sol