Custom Sorting

Sorting can apply to more than just numbers. For example, many solutions to Wormhole Sort involve first sorting the list of edges by their weight.

For example, the sample case gives us 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

We will describe several ways to do this below.

Copy
edge_num = 4

edges = []
for _ in range(edge_num):
	a, b, width = [int(i) for i in input().split()]
	edges.append((width, a, b))
edges.sort()

for e in edges:
	print(f"({e[1]}, {e[2]}): {e[0]}")

Comparators

Most 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.

Copy
class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width


edge_num = 4
edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=lambda e: e.width)

for e in edges:
	print(f"({e.a}, {e.b}): {e.width}")

Copy
from functools import cmp_to_key


class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width

Variations

Sorting in Descending Order

Sorting by Multiple Criteria

Now, suppose we wanted to sort a list of Edges in ascending order, primarily by width 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.

Copy
from functools import cmp_to_key


class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width

Try this slightly modified version of the sample input:

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

While edges with width $3$ and $10$ will still assume the same positions, edges $\{2, 2, 7\}$ and $\{1, 3, 7\}$ will swap in the final ordering with the inclusion of the second criterion.

Coordinate Compression

Coordinate compression describes the process of mapping each value in a list to its index if that list was sorted. For example, the list $\{7, 3, 4, 1\}$ would be compressed to $\{3, 1, 2, 0\}$. Notice that $1$ is the least value in the first list, so it becomes $0$, and $7$ is the greatest value, so it becomes $3$, the largest index in the list.

When we have values from a large range, but we only care about their relative order (for example, if we have to know if one value is above another), coordinate compression is a simple way to help with implementation. For example, if we have a set of integers ranging from $0$ to $10^9$, we can't use them as array indices because we'd have to create an array of size $10^9$, which would cause an MLE verdict. However, if there are only $N \leq 10^6$ such integers, we can coordinate-compress their values, which guarantees that the values will all be in the range from $0$ to $N-1$, which can be used as array indices.

Example 1

A good example of coordinate compression in action is in the solution of USACO Rectangular Pasture. Again, we won't delve into the full solution but instead discuss how coordinate compression is applied. Since the solution uses 2D-prefix sums (another Silver topic), it is helpful if all point coordinates are coordinate-compressed to the range $0$ to $N-1$ so they can be used as array indices. Without coordinate compression, creating a large enough array would result in a Memory Limit Exceeded verdict.

Below you will find the solution to Rectangular Pasture, which uses coordinate compression at the beginning. Observe how a custom comparator is used to sort the points:

Copy
import sys

input = sys.stdin.readline

n = int(input().strip())
points = [list(map(int, input().strip().split())) for _ in range(n)]

points.sort(key=lambda i: i[1])
for i in range(n):
	points[i][1] = i + 1

The solution to Rectangular Pasture directly replaces coordinates with their compressed values, and forgets the real values of the coordinates because they are unnecessary. However, there may be problems for which we need to also remember the original values of coordinates that we compress.

Example 2

This problem will require prefix sums and coordinate compression. However, the implementation of coordinate compression in this solution will also require remembering values in addition to compressing them (as opposed to just replacing the original values, as in the last problem). If you just want to focus on the implementation of coordinate compression and how it can switch between compressed indices and original values, see the contracted code below. indices is a list of values that need to be compressed. After it gets sorted and has duplicate values removed, it is ready to use. The method getCompressedIndex takes in an original value, and binary searches for its position in indices to get its corresponding compressed index. To go from a compressed index to an original value, the code can just access that index in indices.

We also provide a more detailed explanation:

Copy
N, Q = map(int, input().split())

coordinates = {-1}  # dummy coordinate to the left of everything
updates = dict()
queries = []

for n in range(N):  # read updates
	left, right, value = map(int, input().split())
	coordinates.add(left)
	coordinates.add(right)

Problems

Quiz