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:
- Case 1) \(a_i\leq\mathbf{m}_1\leq\mathbf{m}_2\)
- Case 2) \(\mathbf{m}_1\leq a_i\leq\mathbf{m}_2\)
- Case 3) \(\mathbf{m}_1\leq\mathbf{m}_2\leq a_i\)
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:
- Case 1) \(a_i\leq\mathbf{m}_1\leq\mathbf{m}_2\leq\mathbf{m}_3\)
- Case 2) \(\mathbf{m}_1\leq a_i\leq\mathbf{m}_2\leq\mathbf{m}_3\)
- Case 3) \(\mathbf{m}_1\leq\mathbf{m}_2\leq a_i\leq\mathbf{m}_3\)
- Case 4) \(\mathbf{m}_1\leq\mathbf{m}_2\leq\mathbf{m}_3\leq a_i\)
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