CLRS Solutions | Problem 8-4 | Sorting in Linear Time

Water jugs

Suppose that you are given $n$ red and $n$ blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.

Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.

Describe a deterministic algorithm that uses $\Theta(n^2)$ comparisons to group the jugs into pairs.

Prove a lower bound of $\Omega(n \lg n)$ for the number of comparisons that an algorithm solving this problem must make.

Give a randomized algorithm whose expected number of comparisons is $O(n \lg n)$, and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?

The constraint that makes this problem interesting is the cross-color restriction: we can only compare a red jug against a blue jug, never two jugs of the same color. This rules out standard sorting approaches that compare elements freely, but a quicksort-style strategy adapts naturally.

A. Deterministic $\Theta(n^2)$ algorithm

The simplest approach: pick each red jug in turn and compare it against every blue jug until finding its match. For the first red jug, this takes at most $n$ comparisons. For the second, at most $n - 1$ (since one blue jug has been matched). Continuing this way, the total is at most $n + (n-1) + \cdots + 1 = \Theta(n^2)$.

B. Lower bound of $\Omega(n \lg n)$

We use a decision tree argument. The problem requires determining a bijection between $n$ red and $n$ blue jugs. There are $n!$ possible matchings, so any algorithm must distinguish between $n!$ outcomes.

In the decision tree model, each comparison has three outcomes (red holds more, blue holds more, or equal), so the tree has branching factor 3. A ternary tree of height $h$ has at most $3^h$ leaves. We need:

\[3^h \geq n! \implies h \geq \log_3(n!) = \Omega(n \lg n)\]

C. Randomized $O(n \lg n)$ expected-time algorithm

The approach mirrors randomized quicksort. Pick a random red jug as pivot, partition the blue jugs by comparing each against it (finding the matching blue jug along the way), then use that matching blue jug to partition the red jugs. This splits both colors into “smaller” and “larger” groups that can be matched recursively.

$$\textsc{Match-Jugs}(R, B)$$$$\begin{aligned} 1& \quad \textbf{if }\,R\textbf{ and }\,B\,are\,\text{empty} \\ 2& \quad \qquad \textbf{return } \\ 3& \quad pivot\,=\,random\,element\,\text{from}\,R \\ 4& \quad \text{partition}\,B\,\text{into}\,B_{less,}\,\,\,b_{match,}\,\,\,B_{greater}\,\text{using}\,pivot \\ 5& \quad \text{partition}\,R\,-\,{pivot}\,\text{into}\,R_{less,}\,\,\,R_{greater}\,\text{using}\,b_{match} \\ 6& \quad \text{output}\,pair\,(pivot, \, b_match) \\ 7& \quad \textsc{Match-Jugs}(R_{less}, \, B_{less}) \\ 8& \quad \textsc{Match-Jugs}(R_{greater}, \, B_{greater}) \\ \end{aligned}$$

Partitioning blue jugs takes $n - 1$ comparisons, and partitioning red jugs takes another $n - 1$. So each level of recursion uses $O(n)$ comparisons total. The expected recursion depth follows the same analysis as randomized quicksort: since the pivot is chosen randomly, the expected split is balanced, giving $O(\lg n)$ expected levels.

Total expected comparisons: $O(n \lg n)$. In the worst case (always picking the smallest or largest jug as pivot), the recursion depth is $n$ and the total comparisons are $\Theta(n^2)$, just like quicksort.

Problem 8-4

A. Deterministic \(\Theta(n^2)\) algorithm

B. Lower bound of \(\Omega(n \lg n)\)

C. Randomized \(O(n \lg n)\) expected-time algorithm