x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 396

# simple algorithm

hi,
what is the most efficient way/algorithm to sort 4 numbers? i will appreciate any algorithmic approach rather than language dependent ones.
thanks
0
omavideniz
• 4
• 3
• 2
• +5
1 Solution

Commented:
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
0

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

Analyst ProgrammerCommented:
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
0

Commented:
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.
0

Commented:
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.

0

Author Commented:
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.
0

Commented:
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...

0

Commented:
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.

0

Commented:
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

0

Commented:
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.

0

Commented:
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).

0

Commented:
>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...

0

Commented:
omavideniz,

The solution I am proposing has several "efficiency" advantages:
1) Speed
2) Low memory
3) Requires only 3 statements
4) It will put the numbers in the right order
5) It won't do anything if its already in the right order

Here are the three statements, I will word them in English because it will work for any language.  I will refer to the four numbers as A, B, C and D.  Remember that comparing two numbers is the most efficient thing that a computer does.

Statement #1

if A is greater than B
move A to WorkArea
move B to A
move WorkArea to B

Statement #2

if B is greater than C
move B to WorkArea
move C to B
move WorkArea to C

Statement #3

if C is greater than D
move C to WorkArea
move D to C
move WorkArea to D

Those are the only three statements that you will ever need for four numbers and this is how you make it happen....

Do Statement 1
Do Statement 2
Do Statement 3
Do Statement 1 again
Do Statement 2 again
Do Statement 1 for the third time

That's all there is to it.  What's really nice is that NONE of the statements will actually move anything if things are already in the right order.  This method will always move the fewest numbers possible.  The only "extra" memory you will require is for the WorkArea which should be of the same "type" as your other four numbers.  But this is far less overhead than is required for an array because the same WorkArea is used for all moves.

After these statements have been executed you will have A as the lowest number and B as the next lowest number etc. in other words:

A < B < C < D   or,  D > C > B > A    or however you wish to look at it. They mean the same thing.

or, if any of the numbers are of the same value as another number they will always be in the right order too.

*********************************************************

-Roger

P.S. There is one other possible efficiency you could add to the algorithm but for only 4 numbers I don't think you will really be gaining anything.

0

Commented:
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
0

Commented:
omavideniz,
It seems that you have more than one solution to your problem here.
If not, you should accept one of the solutions and close the thread.

Good Luck.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 4
• 3
• 2
• +5
Tackle projects and never again get stuck behind a technical roadblock.