Assume that there is a comparison operator with a switch on it. The comparison o
ID: 3868425 • Letter: A
Question
Assume that there is a comparison operator with a switch on it. The comparison operator can can take upto 3 elements as its input, its output is either the minimum value or the maximum value of the 3 elements, depending on the switch setting (e.g., setting the switch on, its output is the minimum value, otherwise (setting its switch off) its output is the minimum value). If we count each comparison operator with its switch setting as one comparison. Given n greaterthanorequalto 6 elements and assume that n is divisible by 6, what is the minimum number of comparisons needed in order to find the maximum and minimum values from these n elements? Can you propose an algorithm for it? Show the number of comparisons by your algorithm.Explanation / Answer
If n = 12, then first we need to break them, in basket of 3, and find max/min, then those 4 results will again need to be seperated in basket of 3 plus one additional number and then finally 2 numbers should be compared..
so 12 numbers will be broken to
Hence to find max or min from 6 numbers, comparisons needed = 4 + 1 + 1 = 6
A simple code for this algorithm can be as per below:
int findCom(int n) {
int count = 0;
// till single number is left
while( n != 1) {
// 3 numbers can be handles in one try
if(n <= 3) {
count += 1;
// means single number is left
n = 1;
} else {
// break the numbers in basket of 3..
// remaining number which can not go in the
// basket, need to be kept for next round
count += n/3;
n = (n/3) + (n%3);
}
}
return count;
}
============ RESULTS ===============
Comparisons for n=6 are: 3
Comparisons for n=12 are: 6
Comparisons for n=18 are: 9
Comparisons for n=24 are: 12
Comparisons for n=30 are: 15
Comparisons for n=36 are: 18
The results above are for min or max but not for both. For finding both the elements, you need to just double the count.. as we need to run the simulation once with switch off and once with switch on.