[Math] Algorithm to find the second smallest element

algorithmscomputer science

I am having trouble with the following homework assignment:

Give an algorithm that finds the second smallest of n elements in at most
$n + \lceil\log(n)\rceil – 2$ comparisons.

I have been trying to find an algorithm myself, and believe I have to check the elements in pairs and then recurse on the smallest elements. However, when I tried an algorithm like this the amount of comparisons it took where $n + \lceil\log(n)\rceil$ (according to me).

This is the algorithm in question:

1. secondSmallest(A[n])
2.    if A.length >= 2 then
3.       for i = 1 to i = A.length do
4.          if A[i] < A[i + 1] then
5.             B[(i+1)/2] = A[i]
6.             i + +
7.          else
8.             B[(i+1)/2] = A[i + 1]
9.            i + +
10.         endif
11.      return secondSmallest(B[n])
12.    else
13.       if A[1] < A[2] then
14.          return A[2]
16.       else return A[1]
17.       endif
18.    endif

Note: this is pseudocode, and by no means accurate. And the logarithm is a BASE 2 logarithm.

Best Answer

SKETCH: Assuming that you’re allowed to use extra storage, run the comparison as a single elimination tournament, keeping a record of the entries beaten by each winner along the way. (Low number wins.) When you get an overall winner, you have only to identify the winner among the $\lceil \lg n\rceil$ contestants beaten by the overall winner.

Added: On further thought, I see that one doesn’t actually need additional memory, if one rearranges the list. Implement the single elimination tournament as follows.

Suppose that the numbers are $a_0,a_1,\dots,a_{n-1}$. On the first pass compare $a_{2k}$ with $a_{2k+1}$ for $0\le k<(n-1)/2$; if $a_{2k}>a_{2k+1}$, interchange them. On the second pass compare $a_{4k}$ with $a_{4k+2}$ for $0\le k<(n-2)/4$; if $a_{4k}>a_{4k+2}$, interchange the pair $\langle a_{4k},a_{4k+1}\rangle$ with the pair $\langle a_{4k+2},a_{4k+3}\rangle$. On the $i$-th pass compare $a_{2^ik}$ with $a_{2^ik+2^{i-1}}$ for $0\le i<(n-2^{i-1})/2^i$; if $a_{2^ik}>a_{2^ik+2^{i-1}}$, interchange the blocks of length $2^{i-1}$ beginning at $a_{2^ik}$ and $a_{2^ik+2^{i-1}}$. This continues as long as $n-2^{i-1}>0$, i.e., until $n\le 2^{i-1}$; thus, if the last pass is the $m$-th pass, then $2^{m-1}<n\le 2^m$, or $\lceil\lg n\rceil=m$. The smallest number in the set is now $a_0$, and every other number in the set has lost exactly one comparison, so we’ve made $n-1$ comparisons.

The numbers that are now $a_{2^i}$ for $i=0,\dots,m-1$ are the numbers that lost to $a_0$ in direct comparisons; every number in the set that is neither $a_0$ nor one of these $m$ numbers lost a direct comparison to one of these $m$ numbers and therefore cannot be the second-smallest number in the set. Thus, the second-smallest number is the smallest of the $a_{2^i}$ for $i=0,\dots,m-1$. There are $m$ of these numbers, so it takes $m-1$ comparisons to find the smallest.

Altogether, then, this algorithm takes $$(n-1)+(m-1)=n-1+\lceil\lg n\rceil-1=n+\lceil\lg n\rceil-2$$ comparisons, as required.

Related Question