2
$\begingroup$

For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd).
However, I fail to understand the solution given in TAOCP.

Problem: Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.

At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?

In other words, given the pairs $(x_i, x_{i+1})$ for $1 \le i < N$, in random order, where the $x_i$ are distinct, how can the sequence $x_1 x_2 \ldots x_N$ be obtained, restricting all operations to serial techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when there is no easy way to to tell which of two given keys precedes the other.


Solution by Norman Hardy, c. 1967: Make another copy of the input file; sort one copy on the first components and the other on the second. Passing over these files in sequence now allows us to create a new file containing all pairs $(x_i, x_{i+2})$ for $1 \le i \le N-2$ and to identify $(n-1,x_{n-1})$. The pairs $(n-1, x_{n-1})$ and $(n,x_n)$ should be written on still another file.

The process continues inductively. Assume that file F contains all pairs $(x_i,x_{i+t})$ for $1 \le i \le n - t$, in random order, and that file $G$ contains all pairs $(i,x_i)$ for $n-t < i \le n$ in order of the second components. Let $H$ be a copy of file $F$, and sort $H$ by first components, $F$ by second. Now go through $F$, $G$, and $H$, creating two new files $F'$ and $G'$, as follows. If the current records of files $F$, $G$, $H$ are, respectively $(x,x')$, $(y,y')$, $(z,z')$, then:

  1. If $x' = z$, output $(x,z')$ to $F'$ and advance files $F$ and $H$.

  2. If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.

  3. If $x' > y'$, advance file $G$.

  4. If $x' > z$, advance file $H$.

When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.

So here is my question:

  1. If $x' > y'$, advance file $G$.
  2. If $x' > z$, advance file $H$.

What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is it referring to string size?

$\endgroup$
  • $\begingroup$ @Raphael Didn't try too hard: while the 1st edition is on the shelf as often as not, I didn't even think of possible discrepancies from the 2nd, which I don't have equally convenient access to. That said, I'd denote the quote slightly differently (Volume immediately following the title, TAoCP, Ans. to Ex. 24 in Ch. 5). The lines were out of sequence before the edit, in sequence (and numbered correctly) after. No "comparison operator glyph" is used in the problem statement, a simple > as shown in the solution sketched and attributed to N. Hardy. $\endgroup$ – greybeard Jan 26 '17 at 21:41
  • $\begingroup$ @greybeard Oh, the two copies where in different order. I see, should have looked at the full diff. Never mind! Agree reg. the title; edited. $\endgroup$ – Raphael Jan 26 '17 at 22:12
  • $\begingroup$ (@Raphael: the fun thing about Knuth's presentation is the order i) $\text{If } x' = z…F \text{ and } H \text{ ii) If } x' = y'…F \text{ and } G$ ("out of alphabetical order", but simpler condition first), followed by iii) and iv) as 3. & 4. above (in order). Anybody's guess…) $\endgroup$ – greybeard Jan 26 '17 at 22:25
  • $\begingroup$ @greybeard The two steps seem independent, so the order probably does not matter? More interesting question: x' is part of the "current record" of file F. After 1., has x' changed by advancing F (still "current") or not? If you'd code it with current standards, the latter; but I'd have to think or test in more detail to make sure. $\endgroup$ – Raphael Jan 27 '17 at 6:59
  • $\begingroup$ @Raphael: still "current" - current one, always, different from before or not, the way I read it. advancing F (or G, H, at that): between iterations or as last part of step? (and why doesn't H have to be replaced?) I can't remember implementing this… $\endgroup$ – greybeard Jan 27 '17 at 8:14
6
$\begingroup$

What does > denote here?

It's not stated explicitly, but a reasonable meaning can be inferred from context.

The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.

For instance, if we wanted to sort natural numbers in increasing order, $>$ would mean the usual. I we wanted to sort them in decreasing order, you'd have to replace $>$ by $<$ in the solution.

$\endgroup$
  • $\begingroup$ I assume you have understood the solution. Is it possible to explain this with an example by trying to sort input {(b,c),(a,b),(d,e),(c,d)} to {(a,b),(b,c),(c,d),(d,e)}? I have a naive approach using bit array, swapping and shifting which could take O(n^2) complexity in the worst case. $\endgroup$ – noman pouigt Jan 25 '17 at 8:42
  • $\begingroup$ @nomanpouigt I suggest you try to execute the algorithm on paper yourself. If you get stuck, post a new question with the details! That is, don't just ask for somebody to play TM simulator for you. Instead, make sure you have a question. $\endgroup$ – Raphael Jan 26 '17 at 21:12
  • $\begingroup$ nice. I will soon post a question. I will show my approach and ask someone to explain this as i am puzzled by the way solution is written like "If x′=z, output (x,z′) to F′ and advance files F and H.". I don't know if it is appending x and z′ pair or individual elements. $\endgroup$ – noman pouigt Jan 26 '17 at 21:24
  • $\begingroup$ @nomanpouigt The text very clearly states that these new files contain pairs. $\endgroup$ – Raphael Jan 26 '17 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.