Solved

simple algorithm

Posted on 2002-05-19
15
379 Views
Last Modified: 2010-04-17
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
Comment
Question by:omavideniz
  • 4
  • 3
  • 2
  • +5
15 Comments
 
LVL 22

Expert Comment

by:CJ_S
ID: 7019910
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 Comment

by:omavideniz
ID: 7020001
but i'm not looking for a general way but a specific method to sort only 4 numbers.
0
 
LVL 16

Expert Comment

by:Peter Kwan
ID: 7020698
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
 
LVL 47

Expert Comment

by:schwertner
ID: 7020822
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
 
LVL 2

Expert Comment

by:jonnin
ID: 7021294
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 Comment

by:omavideniz
ID: 7021440
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
 
LVL 2

Expert Comment

by:jonnin
ID: 7022502
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
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 2

Expert Comment

by:jonnin
ID: 7023794
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
 
LVL 100

Expert Comment

by:mlmcc
ID: 7025668
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
 
LVL 3

Expert Comment

by:ygal02
ID: 7026402
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
 
LVL 2

Expert Comment

by:jonnin
ID: 7026842
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
 
LVL 3

Expert Comment

by:ygal02
ID: 7027020
>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
 

Accepted Solution

by:
RSchafer earned 50 total points
ID: 7035607
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
 
LVL 100

Expert Comment

by:mlmcc
ID: 7037632
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
 
LVL 3

Expert Comment

by:ygal02
ID: 7038594
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.
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Reading variable length EBCDIC in SAS 9 79
Fibonacci challenge 11 84
tidtcpserver connection lost handle 2 49
Path to Python 9 49
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now