Suppose you have N rational numbers r1, r2, r3, ...rN, whose numerators and deno

Question

Suppose you have N rational numbers r1, r2, r3, ...rN, whose numerators and denominators are all between 1 and N; you may assume all the rational numbers have value at least 1. Show how to sort these numbers in linear time, assuming that any operations on the numerators or denominators (adds, subtracts, multiplies,
integer divides, and integer mod operations) take constant time. Hint: Linear-time sorts are generally done by radix sort. Suppose ri - rj > 0. What is the minimum value of ri - rj?

Explanation / Answer

You need some sort of radix value to organize a finite number of buckets. See Stern-Brocot tree: http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree Now, none of your numbers are less than 1, so we're only concerned with the right side of this tree. Now we want a convenient way to encode the nodes of this tree. I don't think binary is enough to keep it simple because we can from a node, we can have left branches, right branches, OR middle branches. So i would recommend a ternary system. Let our characters be 0, 1, and X. 0 for left branching. 1 for right branching. and X for middle branching. Start at the root (1/1) and encode an X. Then for every type of branching, append accordingly a 0, 1, or X. For a set of rational numbers with numerator and denominator being restricted from 1 to N, you will have encodings of length N (i.e. N buckets). For the wiki i sent you, lets take N to be 4(since that much is visible) 1/1 = 2/2 = 3/3 = 4/4 : XXXX 4/3 : X100 3/2 : X10X 2/1 = 4/2 : X1XX 3/1 : X11X Now bucket sort (radix sort) with the hierarchy 0

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.