simple algorithm

There are several ways.

1) Use an array, then use the sort method
2) loop through each item and put it at the correct place while checking the others
3) use a dictionary object which can sort
4) and more...

It totally depends on the programming languages which is the most efficient.

CJ

but i'm not looking for a general way but a specific method to sort only 4 numbers.

In what sense do you mean "efficient"? We can say an algorithm is "efficient" in either of the following ways:

a) take the least time "in theory", which is programming language independent
b) consume the least memory, which is programming language dependent
c) (a) and (b), which is programming language dependent
d) Simplest way to code in whatever language (coding efficiency), which is programming language independent
e) Other ways that I have not mentioned

You can sort 4 numbers using a block of IF operators. It will be complex but will run fast. Nevertheles the approach to use array and to use the simpliest algorithm like "Bubble" algorithm is also a good solution.

For best speed:

make an array of size 8.

check a vs b and place in sorted order in the middle of the array. Leave 2 spaces in the middle of them!


X X A X X B X X

Now place C where it goes,
in front of a, behind b, or in the middle.
Same for D.  

So maybe it looks like this
 D X A C X B X X

X can be a sentinal value or you can keep the index's manually (done by coding in such a way that you know where things are, not by actually tracking them)

This avoids all swaps, even with xor thats 3 operations.
You still have a lot of compares, 6 of them If I counted correctly (a vs b +1, c Vs a,b +2, d vs a,b,c +3). And this code will be convoluted, hard to extend to 5, 6, etc numbers.  It also avoids excess copying of the numbers by having extra space.

hi pkwan,
actually i'm not looking for the efficiency. in my opinion we couldn't talk about efficieny in a narrow field composed of only 4 numbers. so i'm looking for some optimal method of any kind, of memory optimized, of time optimized, or some kind of mindbending way, a marvellous algorithm not for computers but may be for humans.

thanks for jonnin he put forward a good example.. i'm waiting answers like that, not traditional ways but some creative methods of you or created before. i just want to know about good samples, may be i just want to add to my humble repertoire of methods, algorithms.

Actually, these are often the ones to optimize. A simple task, repeated millions of times, how to keep it from being a bottleneck??  I've spent far more time speeding up a 5 or 6 line inner loop than larger modules that are called infrequently.  

Grey matter (found between your ears) is 3/4 the way for optimal code, but compiler, language, chipset, etc really matter in the end. Maybe moreso on smaller problems where memory access adds noticable time hits.

Where do you stand now? Have you played with recursion, divide and conquor, and the classroom classics??  Sorting methods is a good place to start, for an N sized list.

I will re-think this one tonight and see if I can really make it thin; that above was off the top of my head...

I can't do it in less than 6 compares without some assumptions. But I suspect there is a way to do it in 5, just can't think it up right now. The other parts (using the array to skip swaps, etc) would be the same or similar.

Try something like this

I will assume the values are in A B C D

Compare A & B
  Let E = larger
  Let G = smaller
Compare C & D
  Let F = larger
  Let H = smaller
Compare E & F  (two larger values)
  Let A = Larger
  Let I = smaller
Compare G & H  (two smaller values)
  Let J = larger
  Let D = smaller
Compare I & J
  Let B = larger
  Let C = smaller

A B C D now should be in order  - 5 compares, No swaps, wastes a little memory but if the data is small iin size then no problem.

You could do the same with arrays of data and use a second array of indexes.

Compare Arr(1) and Arr(2)
  Let Order(1) = index of larger
  Let Order(3) = index of smaller
Compare Arr(3) and Arr(4)
  Let Order(2) = index of larger
  Let Order(4) = index of smaller
Compare Arr(Order(1)) and Arr(Order(2))
  Let Order(1) = index of larger
  Let Order(2) = index of smaller
Compare Arr(Order(3)) and Arr(Order(4))
  Let Order(3) = index of larger
  Let Order(4) = index of smaller
Compare Arr(Order(2)) and Arr(Order(3))
  Let Order(2) = index of larger
  Let Order(3) = index of smaller

Order is now
Arr(Order(1))  Arr(Order(2))  Arr(Order(3))  Arr(Order(4))

More efficient than swapping large data types like strings around.

mlmcc
 

Let's {ai}i=1,2,3,4 be the set of numbers to sort, and let {bi}i=1,2,3,4 be the set that will contain the sorted numbers. Since implementing minimum and maximum function between two numbers like: min(a,b), max(a,b) if simple to implement in any language we will assume that they are defined.
Then:

begin;
b1 = min(min(a1,a2),min(a3,a4));
b4 = max(max(a1,a2),max(a3,a4));
b2 = max(min(a1,a2),min(a3,a4));
b3 = min(max(a1,a2),max(a3,a4));
if b2 > b3 then flip b2 and b3;
end;

That's it. The complexity if ofcourse O(1), and independetly of the language or the implementation of the min/max functions I guess this is probably the shortest way.

Good Luck.

min is simple, but it involves at least one comparison. 13 compares for 4 items + a swap?  its almost O(N^2) (closing in on 16 operations) not O(1)...

It is nice, short, simple, and easy to understand. It uses very little memory.

many languages have a built in sort, which is also trivial to code (The O(N^7/6) sort is ~10 lines, about the same if min and max must be written) so it becomes:
sort(list); one line, O(N^7/6) or O(NlogN) for a built in or handwritten (large amount of coding to do well) introsort...

The sorts are overkill here, NlogN is 8  *and* they swap the data (expensive).  But they are scalable for bigger lists of numbers, which can be important.
 

Nicely done mlmcc! I could not find the redundant compare but knew it was possible.

So now we have the primary ways to optimize things:
speed optimized (5 compares, no swaps, etc)
Memory optimized (no wasted space)
Effort optimized (2 ways that are easy to write, counting the sorts).

>min is simple, but it involves at least one comparison. >13 compares for 4 items + a swap?  its almost
>O(N^2) (closing in on 16 operations) not O(1)...

Just to make things clear...
O(1) means a constant number of operation (not one operation), e.g an algorithm performing 1000 operation, but always 1000 operations has a complexity of O(1).
If an algorithm have a constant size of input, it will have a complexity of O(1) no metter what input it gets.
This is changed the moment the input size varies. In this case an algorithm with complexity O(N^2) might with input of 4 elements might run faster than algorithm with complexity O(1) that performs 1000 operations.
The sign O() only shows the order of megnitude of the running time rlative to the input size WITHOUT considering constants (e.g O(N)=O(100N)).
(I had the highest grade in class in this course ;-) )

Good Luck...

Looks like 6 compares and extra assignments to save a few bytes of memory.

Can do my solution the same way

If A < B
 move A to WorkArea
 move B to A
 move WorkArea to B
If C < D
 move C to WorkArea
 move D to C
 move WorkArea to D
If A < C   '(two larger values)
 move C to WorkArea
 move A to C
 move WorkArea to A
If B < D (two smaller values)
 move B to WorkArea
 move D to B
 move WorkArea to D
If B < C
 move B to WorkArea
 move C to B
 move WorkArea to C

Order is now A B C D

mlmcc

omavideniz,
It seems that you have more than one solution to your problem here.
Do you need more information, clearification about any of the solutions ?
If not, you should accept one of the solutions and close the thread.

Good Luck.