0
$\begingroup$

I have 5 numbers which belongs to Z. I am trying to create an algorithm which gives the min and max from the set in only 6 iterations (the least we need to solve the problem).

The purpose in my method is set all numbers in a row from min to max, then the first is min and last is max.

for three numbers is like if a>b then we use a temporary variable d=b b=a a=d now i made a < b for sure. the next iteration is if b>c we do like above, then again a>c and last iteration is a>b again. in this method we get an order for any three numbers when 'a' is min and 'c' is max.

However, for 5 numbers I have an problem when I`m trying to make the numbers in row with only 6 iterations.

Any ideas?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I think you need at least $7$ comparisons to sort $5$ numbers, because with two possible results from each comparison can distinguish $2^6=64$ different orderings with $6$ comparisions but there are $5!=120$ possible orderings. $\endgroup$ – gandalf61 Oct 30 '18 at 15:35
0
$\begingroup$

The problem with your approach is that you try to do more work than necessary(sorting instead of only finding max/min).

My idea is the following:

Let A[0] to A[4] be your 5 numbers. First you set min = max = A[0]. Now you compare A[1] and A[2]. The larger of these numbers you compare with max, the smaller you compare with min. Now you compare A[3] to A[4]. Again you now compare the larger of these numbers to max and the smaller to min. In this way you have exactly 6 comparisons.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.