5
$\begingroup$

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.

  • 0
    Your proposed algorithm doesn't work -- imagine the case where the input is already sorted. Then the first thing that happens in your code is that the true second-smallest element is discarded and never considered again.2012-03-04

2 Answers 2

12

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}, 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.

  • 0
    @Ross: He’s right: I slipped up on the swapping, which must be of blocks of entries rather than just the two being compared. In other words, I’m swapping subtrees, not elements. I think that it’s fixed now.2012-06-28
1

Consider the following list of numbers: $3, 4, 5, 2, 1, 7, 8, 9$.

While passing through the first stage of Brian M. Scott's algorithm above, after each pass the list changes as follows: $ \begin{array}{l|cccccccc} & a_0 & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 \\ \hline \text{start} & 3 & 4 & 5 & 2 & 1 & 7 & 8 & 9 \\ \text{pass 1} & 3 & 4 & 2 & 5 & 1 & \color{blue}{7} & 8 & 9 \\ \text{pass 2} & 2 & 4 & 3 & 5 & 1 & \color{blue}{7} & \color{blue}{8} & 9 \\ \text{pass 3} & 1 & 4 & 3 & 5 & \color{blue}{2} & \color{blue}{7} & \color{blue}{8} & 9 \end{array} $

(The numbers in blue are those that have been compared to the final $a_0$ (that is, $1$) up to (and including) that pass through the algorithm.)

Brian M. Scott then states

The numbers that are now $a_{2^i}$ for $i=0,\ldots,m−1$ are the numbers that lost to $a_0$ in direct comparisons;...

However neither $4$ nor $3$ were ever compared directly to $1$, and the indicies of $7$ and $8$ are not of that form.

Have I missed something?

  • 0
    No, you’ve not missed something; I didn’t state the a$l$gorithm quite right. At each stage you have to interchange *b$l$ocks* rather than just the two numbers being compared. I’ve revised the answer accordingly.2012-06-28