TAOCP 5 Exercise 14

Let the two computers be \(A\) and \(B\).

taocpmathematicsalgorithmsvolume-3medium

Section 5: Introduction to Sorting

Exercise 14. [20] You are working with two computer systems that have different conventions for the "collating sequence" that defines the ordering of alphanumeric characters. How do you make one computer sort alphanumeric files in the order used by the other computer?

Verified: yes
Solve time: 6m35s

Solution

Let the two computers be (A) and (B). Let (\Sigma) be the set of alphanumeric characters. Denote by (<_A) and (<_B) the collating sequences (total orders) on (\Sigma) used by (A) and (B), respectively. We assume (\Sigma) is identical for both systems; if not, the method extends by mapping missing characters to strings that preserve the order, but standard alphanumeric sets coincide.

Because (<_A) and (<_B) are total orders on the same finite set, there exists a unique order‑preserving bijection (\varphi : \Sigma \to \Sigma) such that for all (a,b \in \Sigma), [ a <_B b \quad\Longleftrightarrow\quad \varphi(a) <_A \varphi(b). ] Concretely, if the elements of (\Sigma) are ranked (1,2,\dots,M) in increasing order under (<_B) and under (<_A), then (\varphi) maps the element of rank (r) in (<_B) to the element of rank (r) in (<_A). Extend (\varphi) to strings in (\Sigma^*) characterwise: [ \varphi(c_1 c_2 \dots c_n) = \varphi(c_1)\varphi(c_2)\dots\varphi(c_n). ]

For any two strings (x, y \in \Sigma^*), let (x <{\text{lex},B} y) denote lexicographic order under (<B), and similarly for (<{\text{lex},A}). We claim [ x <{\text{lex},B} y \quad\Longleftrightarrow\quad \varphi(x) <_{\text{lex},A} \varphi(y). ] Proof: Let (i) be the first position where (x) and (y) differ; if no such position exists, the shorter string is smaller and (\varphi) preserves lengths. At position (i) we have (x_i <_B y_i). By construction (\varphi(x_i) <A \varphi(y_i)), while for all (j < i) we have (\varphi(x_j)=\varphi(y_j)). Hence (\varphi(x) <{\text{lex},A} \varphi(y)). The converse follows by applying (\varphi^{-1}).

Therefore, to sort a file of records on computer (A) in the order that computer (B) would produce:

  1. For each record, compute the transformed key (K' = \varphi(K)).
  2. Sort the records on (A) using (K') as the key (the sort routine compares keys according to (<_{\text{lex},A})).
  3. The records are now in the desired order. If the original character representation is required (e.g., to transfer the file to (B)), replace each transformed key by (\varphi^{-1}(K') = K), or simply retain the original keys as satellite data and output them.

This method requires (O(L)) time per key to apply (\varphi) (where (L) is the key length) plus the time of the sort, and uses a translation table of size (|\Sigma|). It works for any stable or unstable sorting algorithm because (\varphi) is a strict order isomorphism between the two key spaces.

This completes the proof. ∎