Sorting Without Comparison
-
You are given two numbers (a, b) and you wish to assign one each to (A, B)
such that A<=B. That is, you want A to equal the minimum of a and b, and
B to equal the maximum of a and b. How can you write A=f(a,b), and B=g(a,b,A)
to correctly assign the values? Try to make functions f and g as simple as
possible.
-
Can you extend the above result for three original numbers (a, b, and c)
to be assigned to A<=B<=C?
-
Can you extend it to four numbers simply?
- Is there a general approach for more numbers, or is a repetitive
method required?
Source: College homework problem.
Solutions were received from Ravi Subramanian, Philippe Fondanaiche,
and Jonty Humphries. Philippe's solutions are below:
- Two terms a,b to be sorted according to A<=B.
The simplest answers are:
- A = [a + b - abs(b - a)]/2 with abs(b - a) = absolute value of b - a
- B = a+b-A
- Three terms a,b,c to be sorted according to A<=B<=C.
-
A = 1/2*[1/2*[a + b - abs(b-a)] + c - abs(1/2*[a + b - abs(b-a)] - c)
- C = 1/2*[1/2*[a + b + abs(b-a)] + c + abs(1/2*[a + b + abs(b-a)] - c)
- B = a + b + c - A - C
- Four terms a,b,c,d to be sorted according to A<=B<=C<=D.
- A = 1/4*[a+b+c+d-abs(b-a)-abs(d-c) - abs(a+b-c-d-abs(b-a)+abs(d-c))]
- D = 1/4*[a+b+c+d+abs(b-a)+abs(d-c) + abs(a+b-c-d+abs(b-a)-abs(d-c))]
It appears that A is equal to min[min(a,b),min(c,d)]
and D is equal to max[max(a,b),max(c,d)].
Therefore B and C can be expressed through
max[min(a,b),min(c,d)] and min[max(a,b),max(c,d)].
-
X = max[min(a,b),min(c,d)]
= 1/4*[a+b+c+d-abs(b-a)-abs(d-c) + abs(a+b-c-d-abs(b-a)+abs(d-c))]
-
Y = min[max(a,b),max(c,d)]
= 1/4*[a+b+c+d+abs(b-a)+abs(d-c) - abs(a+b-c-d+abs(b-a)-abs(d-c))]
-
Therefore C = 1/2*[X+Y+abs(X-Y)] and B = a+b+c+d-A-C-D.
Mail to Ken