TAOCP 5.2.2 Exercise 33

We are given a table $A[1 \ldots N]$ of numbers.

taocpmathematicsalgorithmsvolume-3simple

Section 5.2.2: Sorting by Exchanging

Exercise 33. ▶ [15] Design an algorithm that rearranges all the numbers in a given table so that all negative values precede all nonnegative ones. (The items need not be sorted completely, just separated between negative and nonnegative.) Your algorithm should use the minimum possible number of exchanges.

Verified: no
Solve time: 54s

Solution

We are given a table $A[1 \ldots N]$ of numbers. We must rearrange it in place so that every negative element precedes every nonnegative element, using the minimum possible number of exchanges.

Let $k$ be the total number of negative elements in the table. In the final configuration the first $k$ positions must contain exactly the $k$ negative elements; the remaining $N-k$ positions must contain the nonnegative elements. Initially, let $m$ be the number of nonnegative elements that lie in the first $k$ positions. Because there are exactly $k$ negative elements in total, the last $N-k$ positions must contain exactly $m$ negative elements. Thus $2m$ elements are out of place. Each exchange can correct at most two misplaced elements (by swapping a misplaced nonnegative on the left with a misplaced negative on the right). Hence any algorithm requires at least $m$ exchanges. The following algorithm achieves exactly $m$ exchanges, which is therefore optimal.

Algorithm P (Partition by sign).

P1. [Initialize.] Set $i \leftarrow 1$, $j \leftarrow N$.

P2. [Scan left.] While $i \le j$ and $A[i] < 0$, set $i \leftarrow i + 1$.
If $i > j$, terminate.

P3. [Scan right.] While $i \le j$ and $A[j] \ge 0$, set $j \leftarrow j - 1$.
If $i > j$, terminate.

P4. [Exchange.] Exchange $A[i] \leftrightarrow A[j]$.
Set $i \leftarrow i + 1$, $j \leftarrow j - 1$.
Return to step P2.

Invariant. At the start of each iteration of P2 (and after the initialization):

  • $A[1 \ldots i-1]$ are all negative,
  • $A[j+1 \ldots N]$ are all nonnegative,
  • the subarray $A[i \ldots j]$ is the unprocessed part.

Proof of correctness. The invariant holds initially because $i=1$ and $j=N$ make the two guaranteed regions empty. Step P2 extends the left region as long as it sees negatives; if it stops because $i>j$, the whole array is processed and the invariant implies the array is correctly partitioned. Step P3 symmetrically extends the right region. If it stops with $i \le j$, we have $A[i] \ge 0$ and $A[j] < 0$, so exchanging them places a negative into the left region and a nonnegative into the right region, preserving the invariant after $i$ and $j$ are moved inward. Termination occurs when $i > j$; then the invariant covers the entire array, so all negatives precede all nonnegatives. ∎

Minimality of exchanges. Each execution of P4 exchanges a nonnegative found in the left part with a negative found in the right part. The algorithm performs exactly one exchange for each such pair. The number of such pairs is precisely $m$, the number of nonnegatives initially in the first $k$ positions (equivalently, the number of negatives initially in the last $N-k$ positions). Since at least $m$ exchanges are necessary, the algorithm uses the minimum possible number. ∎

Notes

The algorithm is essentially the partition step of Hoare's quicksort (Section 5.2.2) with the pivot value chosen as $0$. It runs in $O(N)$ time, makes exactly $m$ exchanges, and examines each element at most once. The optimality proof is independent of the initial order and holds for any arrangement.