Contents
raw book

Determining the smallest element of an array is an easy task. If we want to find the second smallest element, we could use two iterations of bubble-sort, since the first \(k\) elements are at the right place after \(k\) iterations already. This however modifies the original array. The following is a derivation of an alternative algorithm, which does not touch the array.

Let the array be \(a_1, a_2, ..., a_n\) and let \(\mathbf{m}_1\) and \(\mathbf{m}_2\) the smallest and the second smallest element, such that \(\mathbf{m}_1\leq\mathbf{m}_2\). We now can construct three cases:

What we do now is modifying \(\mathbf{m}_1\) and \(\mathbf{m}_2\) as we linearly go through the array. That is, we move new elements at the top of \(\mathbf{m}\), seeing it as a fifo. An implementation can then look as follows:

m_1 = min(a_1, a_2)
m_2 = max(a_1, a_2)

for i = 3:n
  if a_i <= m_1
    m_2 = m_1
    m_1 = a_i
  else if a_i <= m_2
    m_2 = a_i
  end
end

Third smallest element in array

The idea can be extended to an arbitrary number of top elements, but note that the overall complexity increases. However, let \(\mathbf{m}_3\) be the third smallest element, we can then make four cases:

Searching for the third smallest element in linear time can then be implemented like this:

m_1 = min(a_1, a_2, a_3)
m_3 = max(a_1, a_2, a_3)
m_2 = a_1 + a_2 + a_3 - m_1 - m_3

for i = 4:n
  if a_i <= m_1
    m_3 = m_2
    m_2 = m_1
    m_1 = a_i
  else if a_i <= m_2
    m_3 = m_2
    m_2 = a_i
  else if a_i <= m_3
    m_3 = a_i
  end
end