patternMinor
Finding Second large element from a set of 4 element
Viewed 0 times
largeelementsecondfindingfromset
Problem
Is there any special algorithm of lowest complexity for finding 2nd largest element from a set of 4 elements?
Solution
It is known that the exact number of comparisons needed to find the second largest element out of $n$ elements is exactly
$$
n-2+\lceil \log_2 n \rceil.
$$
See for example Jeff Erickson's notes. In our case, this gives $4-2 + \lceil 2 \rceil = 4$ comparisons.
Here is a matching algorithm for $4$ elements. Let the elements be $a,b,c,d$, which we assume to be distinct for simplicity.
More generally, if $n$ is a power of $2$, here is how to find the second largest element in $n-2+\log_2 n$ comparisons. First you form a "tournament" by comparing the elements in pairs, then comparing the winners in pairs, and so on, until you find the maximum. This takes $n-1$ comparisons. Then you find the maximum among all $\log_2 n$ elements which "lost" to the maximum, using $\log_2 n - 1$ comparisons.
If $n$ is not a power of $2$ then you add dummy elements with value $-\infty$ to pad the list to the closest power of $2$, and proceed as before. The first phase will take only $n-1$ comparisons (since comparisons with dummy elements need not be performed), and the second will take $\lceil \log_2^n \rceil - 1$ in the worst case (depending on the number of dummy elements which "lost" to the maximal element).
$$
n-2+\lceil \log_2 n \rceil.
$$
See for example Jeff Erickson's notes. In our case, this gives $4-2 + \lceil 2 \rceil = 4$ comparisons.
Here is a matching algorithm for $4$ elements. Let the elements be $a,b,c,d$, which we assume to be distinct for simplicity.
- Compare $a$ and $b$. Without loss of generality, $a > b$.
- Compare $c$ and $d$. Without loss of generality, $c > d$.
- Compare $a$ and $c$. Without loss of generality, $a > c$.
- Compare $b$ and $c$, and return the maximum.
More generally, if $n$ is a power of $2$, here is how to find the second largest element in $n-2+\log_2 n$ comparisons. First you form a "tournament" by comparing the elements in pairs, then comparing the winners in pairs, and so on, until you find the maximum. This takes $n-1$ comparisons. Then you find the maximum among all $\log_2 n$ elements which "lost" to the maximum, using $\log_2 n - 1$ comparisons.
If $n$ is not a power of $2$ then you add dummy elements with value $-\infty$ to pad the list to the closest power of $2$, and proceed as before. The first phase will take only $n-1$ comparisons (since comparisons with dummy elements need not be performed), and the second will take $\lceil \log_2^n \rceil - 1$ in the worst case (depending on the number of dummy elements which "lost" to the maximal element).
Context
StackExchange Computer Science Q#47203, answer score: 4
Revisions (0)
No revisions yet.