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.

$\endgroup$
8
  • 1
    $\begingroup$ Is that supposed to be a natural logarithm? Or base 2 perhaps? $\endgroup$ Commented Mar 4, 2012 at 14:53
  • $\begingroup$ What about binary searching for the smallest element using lg(n) comparisons, removing the smallest element from the array, and then do another binary search on the array using lg(n) comparisons and returning the smallest element. That would be lg(n) + lg(n) comparisons. $\endgroup$
    – SuprDewd
    Commented Mar 4, 2012 at 14:59
  • 1
    $\begingroup$ Oh, I am indeed very sorry. It is supposed to be a base 2. $\endgroup$
    – Ruddie
    Commented Mar 4, 2012 at 15:00
  • 1
    $\begingroup$ @SuprDewd Yes, I found that myself to. But we are meant to find one that takes n+lg(n)-2. Mainly because that would in fact be faster then your solution (since we would have to move all elements when doing that) $\endgroup$
    – Ruddie
    Commented Mar 4, 2012 at 15:04
  • 2
    $\begingroup$ @SuprDewd That requires the array to be sorted. It can be done in $n + \lg(n) - 2$ comparisons for any input array. $\endgroup$ Commented Mar 4, 2012 at 15:09

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ You mean $\lceil \log n\rceil$, correct? $\endgroup$
    – Mike
    Commented Mar 4, 2012 at 15:53
  • $\begingroup$ @Mike: I sure do; thanks. Fixed. $\endgroup$ Commented Mar 4, 2012 at 16:06
  • $\begingroup$ So, you first get the smallest element in the array, taking n comparisons. And then you use a divide and conquer algorithm to find the smallest one out of the remaining elements (which would then take log(n) comparisons, however since you lack one element it would take log(n)-2 comparisons)? $\endgroup$
    – Ruddie
    Commented Mar 4, 2012 at 17:07
  • 1
    $\begingroup$ @Ruddie: No, that’s not at all what I described. The first pass takes $n-1$ comparisons, arranged in a binary tree; the second pass involves only $\lceil\lg n\rceil$ numbers and does $\lceil\lg n\rceil-1$ comparisons. $\endgroup$ Commented Mar 4, 2012 at 17:19
  • $\begingroup$ In the list of entries beaten by each winner the second smallest element is either first or second so finding it needs only one comparison. $\endgroup$
    – duckstar
    Commented Mar 4, 2012 at 17:45
1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ No, you’ve not missed something; I didn’t state the algorithm quite right. At each stage you have to interchange blocks rather than just the two numbers being compared. I’ve revised the answer accordingly. $\endgroup$ Commented Jun 28, 2012 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .