Basics 0/97

Lesson 8 of 8

Sorting and selection

Sort to put a problem in order: custom keys and comparators, event sweeps, coordinate compression, pair counts in merge sort and quickselect.

5,467 words · 25 min read

Part 1 of 10 Sorting records

Sort records with the library

In this lesson we use sorting to solve problems: we process events in time order, replace large values by small ranks, and find one value of the sorted order without sorting the rest. We begin by reviewing how to tell the library sort which order we want, using a list of records.

Consider the scoreboard of a small contest. Each row has a name, the number of problems solved and a time penalty:

name   solved   penaltyana       3       250bo        4       310cy        3       190di        4       280

In the standings, the row with more problems solved comes first, and between two rows with the same count the lower penalty comes first.

In Python an order is described by a key, a function that is called once on each row, and the rows are sorted by the values it returns. Tuples are compared by their first elements, and by their second elements only when the first are equal, so a key that returns (-row[1], row[2]), the negated solved count and then the penalty, expresses both rules of the standings. The minus sign makes larger counts come first.

The scoreboard sorted in two ways

Sign up to run
rows = [("ana", 3, 250), ("bo", 4, 310), ("cy", 3, 190), ("di", 4, 280)]

by_solved = sorted(rows, key=lambda row: row[1])
print([row[0] for row in by_solved])

standings = sorted(rows, key=lambda row: (-row[1], row[2]))
print([row[0] for row in standings])

Prints ['ana', 'cy', 'bo', 'di'], then ['di', 'bo', 'cy', 'ana'].

The first sort uses the solved count alone, so ana ties with cy and bo with di. Python's sort is stable, which means that rows with equal keys keep their input order: ana stays ahead of cy, and bo ahead of di.

In the standings the penalty decides both ties: di is ahead of bo, and cy ahead of ana.

A library sort makes about nlog⁡2nn \log_2 n comparisons, which is about 3.5×1063.5 \times 10^6 for 200,000 rows. Roughly 10810^8 simple steps fit in one second, so a solution can sort its input first at little cost, and most solutions in this lesson begin that way.

Deeper read: library sorts and counting sort

Python's sort is a merge sort that first looks for stretches of the input that are already in order and merges those. On a list that is already sorted it finds a single stretch and makes only n−1n - 1 comparisons.

Sorts like these are comparison sorts: everything they learn about the values comes from asking whether one goes before another. For every comparison sort there are inputs of nn values that force about nlog⁡2nn \log_2 n comparisons. To see why, fix the sort and the number nn, and give it nn different values. Its first comparison is always between the same two positions, and it has two possible outcomes. Which pair the sort compares next may depend on that outcome, the third comparison on the first two, and so on. So the possible runs of the sort form a binary tree, with a comparison at each branching and a finished run at each leaf.

The nn values can arrive in n!n! different orders, and each order needs a different rearrangement to become sorted. If two orders reached the same leaf, they would get the same rearrangement and one of them would come out unsorted, so the tree has at least n!n! leaves. A binary tree with no leaf deeper than dd levels has at most 2d2^d leaves, so some leaf lies at least log⁡2n!\log_2 n! levels down, and the input that leads there costs that many comparisons. For 200,000 values log⁡2n!\log_2 n! is about 3.2×1063.2 \times 10^6, close to nlog⁡2nn \log_2 n.

When the values are small whole numbers, we can sort without comparing any two of them. Counting sort keeps one counter for each possible value and counts how often each value occurs. For [2, 0, 2, 1], with values from 0 to 2, the counters end as [1, 1, 2]: one 0, one 1 and two 2s. Writing each value as many times as its counter says gives [0, 1, 2, 2].

For nn values between 0 and kk this takes nn steps to count and k+1k + 1 counters to read, so O(n+k)O(n + k) time. That can be far less than nlog⁡2nn \log_2 n without contradicting the argument above, because counting sort never compares two values: the step count[x] += 1 picks one of k+1k + 1 counters at once, where a comparison has only two outcomes. It works only while kk is small enough for the counters to fit in memory. Values up to 10910^9 would need a billion counters. Coordinate compression, later in this lesson, makes such values small.