Logic to compare four values and find the smallest

Question

It is correct to compare 4 values in this way?

Se (A < B && A <  C && A < D){
    Escreva A;
};

Senao Se (B < A && B <  C && B < D){
   Escreva B;
};
Senao Se (C < A && C <  B && C < D){
   Escreva C;
};
Senao Se(D < A && D <  B && D < C){
   Escreva D;
}
Senao{
   Escreva 0;
}

Answer 1

It can optimize and I think there’s a mistake:

Se (A < B && A < C && A < D) {
    Escreva A;
} Senao Se (B < C && B < D) {
   Escreva B;
} Senao Se (C < D) {
   Escreva C;
} Senao {
   Escreva D;
}

I put in the Github for future reference.

If A is no less than the other 3 no longer have to check it. Then the same with B, and finally with C. If none is less than D then D is the smallest. I did not understand why it could result in 0. Only if you had any unspecified requirement.

Answer 2

This even works, if the values are all different (if it has two or more equal values, it will go wrong). However, the number of checks within the Ses will grow unsustainably the more variables you have, because if you have N variable, will need to N² - N tests with relational operators.

Maniero’s approach reduces the number of checks by half ((N² - N) / 2), but there is a simple approach that uses only N - 1 checks:

MenorValor := A
Se (B < MenorValor) MenorValor := B;
Se (C < MenorValor) MenorValor := C;
Se (D < MenorValor) MenorValor := D;
Escreva MenorValor;

Answer 3

Note that the way you implemented it is possible to need more than three comparisons. It is possible to find minimum of four values with only three comparisons in any circumstance (i.e., with better performance), this in several ways.

For example, one can find the minimum "M1" of "A" and "B" (M1=( A<B ? A : B );), then find the minimum "N" of "C" and "M" (M2=( C<M1 ? C : M1 );) and finally return the minimum of "D" and "M2" (return( D<M2 ? D : M2 );).

Another way (which may be better if you can parallelize) is to find the minimum "M" of "A" and "B" (M=( A<B ? A : B );) and at the same time find the minimum "N" of "C" and "D" (N=( C<D ? C : D );), then just return the minimum of "M" and "N" (return( M<N ? M : N );).

If you want to implement this second without using temporary "M" and "N", you can use the following penca of comparisons that uses the same reasoning, but maybe not so well optimized even by good compilers.

if( A<B ){
    if( C<D ) return( A<C ? A : C );
    else return( A<D ? A : D );
}
else {
    if( C<D ) return( B<C ? B : C );
    else return( B<D ? B : D );
}

If you want to generalize the problem to find the minimum of "n" numbers "a[0], a[1], ..., a[n-1]", you can calculate the minimum of them with "n-1" comparisons. One is the following, which is a generalization of the first mentioned algorithm.

T = a[0] ;
for( i=1 ; i<n ; i=i+1 ){
    if( T>a[i] ) T = a[i] ;
}
return T ;

Already the generalization of the second requires recursion, something that is only worth giving to compile optimally (without need of stacking) and in this case it is good that there are means of calculating parallel.

This is done by finding the minimum "M" of the first half of the numbers, the minimum "N" of the second half, and then returning the minimum of "M" and "N", where the recursion stop is the sequence of size one, where the only number worked is the minimum.

Any doubt?