Fastest way to sort 3 values in Java

Question

I have to put 3 values in correct order and print them out to the console.

A solution is to put them into an array and then sort them, but I remember (from school times) that there was faster to compare and order them, however I can't find the correct comparison order.

Could you please show me how to compare 3 values with the minimum number of if statements?

For three items [bogosort](http://en.wikipedia.org/wiki/Bogosort) would do fine. — millimoose, Oct 23 '12 at 22:24
related: [Fastest sort of fixed length 6 int array](http://stackoverflow.com/q/2786899/4279) — jfs, Dec 04 '15 at 14:00

score 21 · Answer 1 · answered Oct 23 '12 at 22:46

21

bubble sort would have only 3 compare ops, and 6 assignments at worst case (it will be very similar if not identical to the behavior of insertion sort in this case):

if (a > b)
   swap(a,b)
if (b > c)
   swap(b,c)
if (a > b)
   swap(a,b)
print a,b,c

It cannot be done in less then 3 compares because there are n!=6 possible permutations for the array, and ceil(log_2(n!)) = 3

answered Oct 23 '12 at 22:46

amit

175,853
27
231
333

Will the downvoter please elaborate? Is it because of the mathematical proof it cannot be better then 3 compares? or because of the algorithm showing it can be achieved within 3 compares? – amit Oct 23 '12 at 22:48
This is basically bubblesort written out. Minsort would let you get rid of one potential swap. – millimoose Oct 23 '12 at 22:50
@millimoose: Yes, it is bubble sort - as it clearly indicated in the first line of the answer. min sort will still need to do 3 compares (find the min - 2 compares, find the new min in the subarray - 1 compare). – amit Oct 23 '12 at 22:52
@amit - 3 Compares is best case scenario here because the set is small. Best case scenario for bubble sort is O(n) so that is in line with expectations. – Travis J Oct 23 '12 at 23:00
Thats not exacly what i wanted, but it does the trick somehow. I could use Arrays.sort, but I wanted to use other method. Thank you. – user1769735 Oct 23 '12 at 23:03
@TravisJ: It does not matter, bubble sort *worst case* is n-1 + n-2 + ... + 1 compare ops (assuming not extra compare for `breaking out` optimization). when `n==3` it will get you (3-1) + (2-1) = 2+ 1 = 3 compare ops. There is no point to talk about big O when dealing with 3 elements. – amit Oct 23 '12 at 23:03
@amit - Bubble sort worst case is O(n^2). There is always a point in talking about time complexity when the topic is optimization. – Travis J Oct 23 '12 at 23:04
1

@TravisJ While the big-O formula is correct, the fact is that the worst case for `3` elements with a sane bubble sort implementation is `3` comparisons and `2` swaps, not `9` of anything. The big-O notation is a drastic simplification of what's usually a much more complicated and more difficult to determine exact formula for the number of operations; the cost of this simplification is that it's allowed to overestimate to various degrees. – millimoose Oct 23 '12 at 23:08
1

@millimoose: there is no compare in swap() - only reads and assignments, making it 3 compares. My solution aimed to show an algorithm with minimum number of COMPARES ("lowest tree") and to show it cannot be done with fewer compares. – amit Oct 23 '12 at 23:09
@amit My point is that your algorithm isn't the "fastest way" (as asked by the OP), because it doesn't optimise for swaps. (FWIW, I didn't downvote your answer.) – millimoose Oct 23 '12 at 23:11
1

@TravisJ: Please read the definition of big O notation again, I elaborated it as a comment to your answer. When talking small scale - big O says NOTHING, since the upper bound definition does not include these cases (from the definition of big O). – amit Oct 23 '12 at 23:14
@amit - Stated already, and clear from analysis that best case was O(n). If you don't understand the difference between best, worst, and average case with time complexity and big o notation then I am not sure how much of this back and forth you are really going to benefit from. – Travis J Oct 23 '12 at 23:19
1

@TravisJ Well, the discussion included too many comments and was thus removed, I want only to add the bottom line, hoping it is accepted. Big O notation says: if `f(x)` is `O(g(x))` - then there are x0,M such that for each x > x0: `|f(x)| < M*g(x)`. If x < x0 - all bets are off. We cannot say anything. For example, the function `f(x) = { if x < 10: x^10 | otherwise: x }`. By definition of big O, we will get that `f(x)` is `O(x)`. That said - I am going to sleep, have work tomorrow. You are more then welcome to open a chat and I'll try to elaborate tomorrow - if you are willing to learn. – amit Oct 23 '12 at 23:35
1

"It cannot be done in less then 3 compares" Yes, it can. Consider `a <= b <= c` or `a > b > c`. It cannot be done in less than 2 compares. – Ecir Hana Feb 19 '15 at 11:04
@EcirHana You cannot give a specific example and say "it works with 2 compares on it" - you need to show a series of 2 compares that works on ALL inputs. This is how lower bound works. Why is sorting is `Omega(nlogn)` problem when clearly you can sort a sorted array in `O(n)`? – amit Feb 19 '15 at 11:13
1

You said that sorting 3 numbers "cannot be done in less then 3 compares", ever. What I said was that if you get lucky, you can spare one compare. – Ecir Hana Feb 19 '15 at 12:12
@EcirHana The implicit intent was worst case complexity, same as sorting an array is Omega(nlogn) problem for worst case complexity – amit Feb 19 '15 at 12:24
"implicit intent" by whom? you? OP? OP said "compare 3 values by minimum values of if"... – Ecir Hana Feb 19 '15 at 12:27
@EcirHana I dare you to find a fewer number of comparisons that solves the problem for every input. The problem statement `Could you please show how to compare 3 values by minimium values of if()?` suggests he needs fewest possible "if statements" (interpeted as comparisons), and it supposed to work for every input. A worst case complexity analysis is a very common implicit assumption in literature, and I am not going to argue about either it's correct or not. – amit Feb 19 '15 at 12:31
Search for "__sort3" in [libcxx](http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm). – Ecir Hana Feb 19 '15 at 12:33
@EcirHana OK, I see a chain of 3 if conditions comparing values that is reachable for the input x<=y, y>z. – amit Feb 19 '15 at 12:37
Ok, whatever. Your answer is wrong. – Ecir Hana Feb 19 '15 at 12:41
@EcirHana I would be happy to agree if you can show me a sorting algorithm for 3 elements that uses less than 3 compares for every input. (Unfortunately, `ceil(log_2(3!)) > 2`, so that won't happen). Good day. – amit Feb 19 '15 at 12:42
@EcirHana Why is his answer wrong? – Koray Tugay Dec 03 '15 at 15:24
@EcirHana best case is 2 comparisons, worst case is 3 comparisons. for best case, your guess for middle value should be true. for example if `a <= b` and `c => b` then you don't need to compare `a` to `c`. however if `b` is not middle then you do 3 comparisons. – M.kazem Akhgary Feb 22 '19 at 20:25

Travis J · Accepted Answer · 2016-11-02T18:54:00.557

10

There is no point in optimizing this. It will not gain any speed. O(n!) for 3 is still only 3*2 = 6 operations. Even O(2^n) is going to be 8. You could really do whatever it takes to sort these 3 values and not see a difference in performance.

edit

int a, b, c, min, max, med;//assume values are there for a b c
if( a > b ){
 if( a > c ){
  max = a;
  if( b > c ){
   med = b;
   min = c;
  }else{
   med = c;
   min = b;
  }
 }else{
  med = a;
  max = c;
  min = b;
 }
}else{
 if( b > c ){
  max = b;
  if( a > c ){
   med = a;
   min = c;
  }else{
   med = c;
   min = a;
  }
 }else{
  med = b;
  max = c;
  min = a;
 }
}

edited Nov 02 '16 at 18:54

answered Oct 23 '12 at 22:23

Travis J

81,153
41
202
273

2

The following code seems not necessary: `if( b > c ){ max = b; min = c; }else{` Because once a is greater than b, but a is not greater than c, then b will never be greater than c. – durban Nov 02 '16 at 16:05
@durban - That is true, this was mostly written to show that explicitly checking all scenarios would not affect the speed of such a small operation. I removed the redundant code. – Travis J Nov 02 '16 at 18:55

score 0 · Answer 3 · answered Dec 03 '15 at 15:26

0

As far as i know, Java uses the Quicksort algorithm for sorting - an already optimized approach. No speed to harvest here!

answered Dec 03 '15 at 15:26

Gewure

1,208
18
31

6

Specifically for boundary cases (like sorting just 3 values). Regular sorting algorithms like quicksort might not perform well – Batavia Dec 04 '15 at 08:34

Fastest way to sort 3 values in Java

3 Answers3

Linked

Related