qsort

qsort is the only sort the C standard library gives you, and in this repository it is the C port's answer to a single line of Python. Nearly every problem below has a Python sibling that wrote sorted(...) — or a set, a Counter or a dict of them, which all amount to the same thing once you port them — and moved on; the C side has to supply a comparator, decide what the array elements actually are, and find somewhere to put the context the comparator needs. That gap — one call versus a design decision — is why qsort shows up as a technique tag at all, and why the same handful of mistakes recur.

The idea

The signature is deliberately type-blind:

void qsort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *, const void *));

qsort knows nothing about your elements except how many bytes each occupies. It reorders them by copying size bytes at a time, and it asks your comparator, through a function pointer, which of two elements comes first: negative if the left one sorts earlier, zero if they are equivalent, positive otherwise. The standard requires only that the result be O(n log n) on average — the name is historical, and a modern libc typically runs introsort or a merge sort rather than plain quicksort.

What the ports use it for is almost never "produce a sorted list". Three jobs cover nearly all of them:

  • Count or collapse duplicates. C has no set and no dict. When the Python sibling wrote len(set(values)), the C port sorts the array and counts the places where an element differs from its predecessor. Problems 757, 221 and 165 all end this way; problem 203 does it over GMP integers, and problem 749 over plain long longs, summing each distinct value once as it scans (749's search finds some numbers more than once). The same scan counts multiplicities as easily as distinct values: after the sort, how many times a value occurred is the length of its run. Problem 348 wants the sums reachable in exactly a given number of ways, and where its Python sibling asked np.unique for counts, the C port sorts the hits and reads each run's length — a Counter with no hash table. Sometimes the run length encodes the answer rather than being it. Problem 842 generates one crossing per pair of crossing diagonals, so a point where k diagonals meet shows up as a run of m = C(k, 2) equal keys. The port inverts that to recover k, and a run whose length is not a triangular number means the snapping went wrong (more on that below), so the port returns an error. Problem 972 goes the other way: a run of s points on one line through an anchor contributes C(s, 2) collinear pairs.
  • Bring equal keys into contiguous runs. Once sorted by a key, a while loop can walk one group at a time. Problems 142, 926 and 1000 all use this run-scan: gather the block of records sharing a key, process it as a unit, advance. Problem 1000 depends on it for correctness: it walks edges in increasing weight, and all the edges of one weight must be applied as a single snapshot so that two of them never chain — only the sort puts them adjacent to be grouped. Sort by a composite key and the runs nest: problem 963's Python groups values in a dict of Counters (outer key → inner value → count), and the port replaces the whole structure with one sort on (outer, inner). A single pass then collapses equal pairs into a weight and records where each outer key's block begins in an offsets array, so "the inner values of key s" is the slice [start[s], start[s + 1]) — the two-level map flattened into two arrays.
  • Create the monotonicity a later search relies on. Problem 143 sorts each adjacency list so membership becomes a binary search instead of a scan; problem 127 sorts candidates by radical so an inner loop can break at the first failure; problem 768 sorts both halves of a meet-in-the-middle table so they can be joined by one two-pointer merge instead of an all-pairs sweep. The sort's n log n is bought to change the inner loop's asymptotics, not to tidy the data.
  • Rank. Sometimes the answer needs each element's position in some order, and the order is expensive to construct but cheap to compare. Problem 941 weights each of N pseudo-random windows by its rank when the windows are ordered by where they occur in a huge de Bruijn sequence. The port never builds the sequence or finds a position. It computes a key per window that sorts in the same order as the windows appear (which necklace's block, then the offset inside it), sorts on that key, and reads off each rank as i + 1. The sort does the work of locating every window.

Problem 52 is the smallest complete example, and it is public, so here it is whole. The digits of n are extracted least-significant-first and sorted into a canonical fingerprint — order out of the extraction is irrelevant precisely because a sort follows:

static int cmp_char(const void *a, const void *b) {
    return (*(const char *)a) - (*(const char *)b);
}
...
qsort(tmp, (size_t)len, 1, cmp_char);

Note the element size of 1: qsort sorts an array of anything, including raw chars, and a digit-permutation test becomes strcmp. The element size does not have to be a sizeof at all. Problem 336 enumerates fixed-length letter arrangements into one flat buffer, n bytes per row, and sorts the rows in place with qsort(level, count, n, compare_rows) and a comparator that is just memcmp over n bytes. That is Python's sorted(list_of_strings) with no per-string allocation and no pointer array: for fixed-width byte strings, memcmp order is lexicographic order.

Make equivalent things equal first

A sort groups elements that compare equal. Usually, though, what the problem cares about is elements that are equivalent: the same line, the same triangle, the same point. So the step before the sort is to rewrite every element into a canonical form, so that two equivalent elements end up identical. Three versions of this appear here, depending on where the ambiguity comes from:

  • Scale and sign. Problem 972 identifies the line through an anchor point and each other point by its integer normal (w1, w2), but (2, -4) and (-1, 2) describe the same line. The port divides by the gcd and fixes the sign before storing the key, and after that two points on one line share a key byte for byte. That is Python's Fraction normalisation done by hand.
  • Order within the element. Problem 998 finds some triangles twice, once from each of two corners. Each side-triple is sorted with a three-element sort3 first, then the triples are sorted as 3-long long rows (qsort(corners, n, 3 * sizeof *corners, cmp_tri), the same trick as 336's rows). The duplicate scan calls cmp_tri itself, as 963 does, and each triangle is counted once. Problem 949 does the same thing for sets. A game form is a pair of option sets, and C has no frozenset, so sort_unique sorts and deduplicates each option list in place. After that, two equal sets are equal arrays, which can be hashed and compared with memcmp. This is what makes 949's interning table work.
  • Floating point. Problem 842's crossing points come out of a double division, so two computations of the same point differ in the last bits, and a comparator on raw doubles would split one run into several. The port rounds each coordinate to a 1e-9 grid with llrint. That is only safe because distinct crossings are known to be much further apart than the grid spacing, and the triangular-run-length check above is what catches the case where that assumption fails.

842 also shows the other half of the habit, which is packing a composite key into one integer. Its snapped coordinates are both below 2^30, so x * 2^32 + y is exact and injective. The point then sorts with the same plain long long comparator as everything else, and the run walk compares with ==. Problem 941 packs (necklace, offset) the same way, as value * SHIFT + offset. The alternative is a struct with a field-by-field comparator, which is what 972 and 949 use for their two-field keys. That is fine, but every equality test in the scan then has to repeat the field list, and that duplication is exactly what can drift out of sync. Packing works when you can prove the bounds. When you can't, use the struct.

Writing the comparator

Do not subtract, except on small types. return *(int *)a - *(int *)b; is the textbook one-liner and it is wrong the moment the values are wide: the difference of two large ints overflows, which is undefined behaviour, and the comparator silently reports the opposite order. Problem 52's cmp_char above gets away with it because digits are chars; every comparator in this repository over long long, int128 or a struct field instead uses the branch-free three-way idiom:

return (x > y) - (x < y);   /* -1, 0, or +1 — no subtraction, no overflow */

Both parenthesised comparisons yield 0 or 1, so the difference is exactly the sign, and the compiler emits it without a branch. Problems 118, 757, 221, 926, 768, 1000, 348, 963, 749, 842, 941 and 949 all carry this exact line. On unsigned keys subtraction does not even overflow — it wraps, so x - y cast to int gives garbage signs — which is why problem 963's comparator on its unsigned long long field compares explicitly too. It is worth making a habit — it costs nothing and removes an entire class of bug.

Give the comparator a total order if you want determinism. qsort is not stable: elements your comparator calls equivalent may come out in any order, and the order can differ between libc versions. When the downstream code cares, add tie-breakers until the order is total. Problem 127 compares by radical and then by index for exactly this reason; problem 165 compares its three-field rational key lexicographically, returning 0 only for genuine equality, which is what makes the following distinct-count scan correct.

Sort indices when the data is in parallel arrays. Problem 464 keeps its points as several long long arrays and sorts an array of int indices, with the comparator dereferencing the key array. Nothing large is copied, the parallel arrays stay aligned, and one array can be sorted by several different keys in turn.

There is nowhere to put context. qsort's comparator takes two element pointers and nothing else — no user-data parameter. Three ways out appear here:

approach seen in cost
a file-scope variable the comparator reads 464 (g_key), 252 (sort_base), 336 (row_width) not reentrant; fine in a single-threaded solve()
a GCC nested function closing over locals 127, 142 a GNU extension, not ISO C
qsort_r / C11 qsort_s — correct, but the argument order differs between glibc and BSD

Problem 464's declaration says the quiet part out loud: qsort has no context pointer without qsort_r; single-threaded solve() only. Writing that comment is the honest version of using a global here — it is a deliberate, scoped exception, not an accident. Problem 336 shows how thin the interface really is: the context its comparator needs is the row width, a number qsort was handed as its own size argument and never passes on.

After the sort

Sorting is the setup; the scan that follows is where the answer comes from, and it has two shapes worth knowing by heart. Counting distinct values:

for (size_t i = 0; i < len; i++)
    if (i == 0 || vals[i] != vals[i - 1]) distinct++;

and compacting in place, which is the same loop writing as it goes (if (i == 0 || v[i] != v[u-1]) v[u++] = v[i];, leaving u as the new length). Problems 221, 180, 143 and 949 use the compacting form because they need the deduplicated array afterwards; 757, 165, 203, 749 and 998 only need the count or the sum, so they scan without writing.

The third shape is the run walk: an outer while that finds the end of the current key's block with an inner while, handles the block, then jumps i to the block's end. It costs one pass and it is how 142, 926, 1000, 464, 348, 963, 842 and 972 all consume their sorted arrays — 348, 842 and 972 need nothing from the block but its length j - i.

The shapes combine. Problem 963's single post-sort pass compacts in place, keeps a weight per surviving element (how many duplicates it absorbed), and notes each outer-key boundary — and it asks "differs from its predecessor?" by calling the comparator itself rather than restating the key fields. Reusing it keeps the scan's notion of equality identical to the sort's, so a key field added to one cannot be forgotten in the other.

If what you want is a lookup rather than a pass, the standard library's bsearch takes the same comparator — sort once, search many times, with one function serving both. Problem 184 pairs them directly.

How to reason about it

The constant factor is the function pointer. Every comparison is an indirect call that cannot be inlined, which is the price of a type-erased sort in C — C++'s std::sort is faster mainly because it inlines the comparison. On a few million elements this is a real but tolerable cost; if the sort is genuinely hot and the keys are small bounded integers, a counting or radix sort beats it outright. Problem 461 is the one port here that pays to escape the indirect call on its own terms: it sorts tens of millions of small records by a double key and hand-writes a typed introsort with the comparison inlined, which is exactly why it is absent from the list below. That is the trade you are making — a page of sorting code, and a comparator you can no longer reuse for bsearch, bought with one saved indirect call per comparison. Almost never worth it; measure before you believe it. Keep the elements small for the same reason: qsort physically moves size bytes per swap, so sorting an array of fat structs is slower than sorting indices into them.

The opposite case, many tiny sorts, also argues against qsort. Problem 998 sorts each of its many per-leg buckets (a few hundred entries at most) with a hand-written insertion sort instead. At that size the call overhead and the indirect comparisons dominate, and the loop moves the bucket's two parallel arrays together, with no index array and no context global. The one qsort in the port is for the large, flat duplicate scan at the end.

Elements must survive a byte-wise move. qsort relocates elements with raw copies, so anything holding a pointer into itself breaks. GMP's mpz_t is fine — it is a struct holding a pointer to separately allocated limbs, so the pointer travels with the struct, which is why problem 203 can qsort an array of them with sizeof(mpz_t) and a mpz_cmp wrapper. A struct with an interior self-reference would not be.

The comparator must be consistent. A comparator that is not a valid ordering — one that says a < b and b < a, or whose result depends on state that changes mid-sort — is undefined behaviour, not merely a wrong answer; qsort may read out of bounds. The globals-for-context pattern above is safe only because the global is set before the call and left alone during it.

Sort inside solve(). A table built and sorted at file scope or in a static initialised once is free from the second benchmark run onward, and the reported timing will understate the real cost. Every array here is allocated, filled, sorted and freed within the call.

And check whether you need the sort at all. For a bounded integer range, a bit array or a direct-indexed counter answers "distinct?" in one linear pass with no comparator — problem 143 uses exactly that for its sum bitset while still sorting its adjacency lists, because the two questions have different shapes. qsort is the general tool; reach for it when the key space is too large or too structured to index directly.

Problems43 / 43

  • ● 0022 — Names Scores
  • ● 0049 — Prime Permutations
  • ● 0052 — Permuted Multiples
  • ● 0054 — Poker Hands
  • ● 0062 — Cubic Permutations
  • ● 0096 — Su Doku
  • ● 0103 — Special Subset Sums: Optimum
  • ● 0107 — Minimal Network
  • ● 0118 — Pandigital Prime Sets
  • ● 0119 — Digit Power Sum
  • ● 0124 — Ordered Radicals
  • ● 0127 — abc-hits
  • ● 0140 — Modified Fibonacci Golden Nuggets
  • ● 0142 — Perfect Square Collection
  • ● 0143 — Torricelli Triangles
  • ● 0152 — Sums of Square Reciprocals
  • ● 0165 — Intersections
  • ● 0177 — Integer Angled Quadrilaterals
  • ● 0180 — Golden Triplets
  • ● 0184 — Triangles Containing the Origin
  • ● 0200 — Prime-proof Squbes
  • ● 0203 — Squarefree Binomial Coefficients
  • ● 0212 — Combined Volume of Cuboids
  • ● 0221 — Alexandrian Integers
  • ● 0248 — Euler's Totient Function Equals 13!
  • ● 0252 — Convex Holes
  • ● 0321 — Swapping Counters
  • ● 0336 — Maximix Arrangements
  • ● 0346 — Strong Repunits
  • ● 0348 — Sum of a Square and a Cube
  • ● 0464 — Möbius Function and Intervals
  • ● 0749 — Near Power Sums
  • ● 0757 — Stealthy Numbers
  • ● 0768 — Chandelier
  • ● 0842 — Irregular Star Polygons
  • ● 0926 — Total Roundness
  • ● 0941 — de Bruijn's Combination Lock
  • ● 0949 — Left vs Right II
  • ● 0963 — Removing Trits
  • ● 0972 — Hyperbolic Plane
  • ● 0998 — Squaring the Triangle
  • ● 1000 — Problem $1000$
  • ● 1003 — Lonely Singles