Minimum and Maximum of a set

Question

I need help at the following:

How can we find the minimum and the maximum of a set of $N$ numbers using $1.5N $ comparisons?

Answer 1

For simplicity, let's assume that $N$ is even:

• Split the set into $\dfrac{N}{2}$ pairs, and for each pair find the minimum and the maximum
• Since we need to perform only one comparison for each pair, this takes $\dfrac{N}{2}$ comparisons

---

After obtaining $\dfrac{N}{2}$ minimum values and $\dfrac{N}{2}$ maximum values:

• Go over all minimum values and find the minimal one using $\dfrac{N}{2}-1$ comparisons
• Go over all maximum values and find the maximal one using $\dfrac{N}{2}-1$ comparisons

---

Altogether, we've performed $\dfrac{N}{2}+(\dfrac{N}{2}-1)+(\dfrac{N}{2}-1)=\dfrac{3}{2}N-2$ comparisons.

If $N$ is odd, then at most $2$ additional comparisons (of the last element in the set, with the minimum value and with the maximum value) will be required in order to ensure the result.