0
$\begingroup$

Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ comparisons in the worst case. (Hint: Also find the smallest element.) [1]

I tried but I have no idea how to, e.g. the best I could do is

//assume n>=2
//A: array of size n 
//returns second smallest in A 
//0 indexing in C++

int second_smallest(int*A,int n){
    queue<int> q;//always keep the size to 2 by push & pop. Also it stores indices. 
    q.push(1);//2nd smallest 
    q.push(0);//smallest
    for(int i=1;i<n;++i){
        if(A[i]<A[q.back()]){
            q.push(i);
            q.pop();
        }
    }
    int i=q.back()+1;//we know for sure A[0],...,A[q.back()-1] are greater than A[q.front()]. And A[q.back()] is the smallest.
    q.push(q.front());//after this line, assume q.back() is 2nd smallest 
    q.pop(); 
    for(;i<n;++i){
        if(A[i]<A[q.back()]){
            q.push(i);
            q.pop();
        }
    }
    return A[q.back()]; 
}

which conducts $(n-1)+(n-2)=2n-3$ comparisons in worst case. When input is uniformly distributed over all permutation the average number of comparisons is $(n-1)+n-E[q.back()]=\frac{3}{2}n-\frac{1}{2}$ where $q.back()$ refers to the one at $(*)$, and we know $E[q.back()]=\frac{1}{n}(1+...+n)=(n-1)/2$.

But this's no where near $n+\lceil\lg n\rceil-2$ so I'm out of idea could someone help?

[1] Introduction to Algorithms,MIT

$\endgroup$

2 Answers 2

1
$\begingroup$

Assume that all elements are distinct (if not, replace each element with a pair $(element, position)$ and perform the comparisons lexicographically) and consider a rooted binary tree $T$ with $n$ leaves in which each vertex has either $0$ or two children and every level, except possibly the last, is completely filled. Arbitrarily associate each leaf of $T$ with a distinct input element.

You can find the minimum by computing, for each interval vertex $v$, the minimum among all the elements associated to the leaves of the subtree of $T$ rooted at $v$. This can be done by performing a postorder visit of $T$: whenever $v$ is visited, let $v_\ell$ and $v_r$ be its two children, compare the elements associated with $v_\ell$ and $v_r$ and let the minimum among the two be the winner; the element associated with $v$ is exactly such winner.

At the end of the visit, the root of the tree will be associated with the minimum element of the input sequence.

Consider now the set $P$ of the vertices that have been associated with the minimum element and notice that they induce a root-to-leaf path in $T$. Let $C(P)$ denote the set of all children of the vertices in $P$. Since the second-smallest element $x$ can only lose against the minimum element, there must be a vertex associated with $x$ among those in $C(P) \setminus P$ (and this set contains no vertex associated with the minimum element). Then, you find the second-minimum of the input sequence be looking for the minimum of the elements associated with the vertices in $C(P) \setminus P$.

The overall number of comparisons is given by the sum of 1) the number of comparisons used to find the minimum, and 2) the number of comparisons needed to handle $C(P) \setminus P$. Regarding 1), we perform exactly $1$ comparison for each internal vertex, for a total of $n-1$ comparisons. Regarding 2), we perform $|C(P) \setminus P| - 1$ comparisons, where $|C(P) \setminus P|$ is at most the depth of $T$, i.e., $|C(P) \setminus P| \le \lceil \log n \rceil$. Then: $$ (n-1) + (|C(P) \setminus P|-1) \le (n-1) + (\lceil \log n \rceil - 1) = n + \lceil \log n \rceil - 2. $$

The above is this is just a handy description for the analysis of the number of comparison. You don't actually need to build and traverse the tree $T$. Here is a possible recursive implementation:

Input: a non-empty list L of distinct elements
Output: the second-minimum in L
Second-Minimum(L):
    (x, S) = Find-Candidates(L)
    Return the minimum in S

Input: a non-empty list L of distinct elements
Output: a pair (x, S), where x is the minimum in L, and S is a set of candidate second-minimum elements
Find-Candidates(L):
    If |L|==1:
        return (x, {}), where x is the only element in L

    Split L into L' and L'' with | |L'| - |L''| | <= 1
    (x', S') = Find-Candidates(L')
    (x'', S'') = Find-Candidates(L'')

    If x' < x'':
        Return (x', S' U {x''})
    Else:
        Return (x'', S'' U {x'})
$\endgroup$
0
$\begingroup$

Based on Steven's great answer, and some modification so that the second minimum is computed "on the fly" (this won't change the number of comparison) below implemented the algorithms in C++ that also prints the tree for visualization

e.g. with input array L = 3,1,5,2,4 the second smallest is 2 and the tree is printed after $90$ degree rotation to the right

                4
        2
                2
1
                5
        1
                        1
                1
                        3

code:

#include <iostream>
#include <stack>
using namespace std;
//declare only 
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order);
void print_in_order(stack<int*>&post_order,int depth);

//L is continuous array starting from indices p to r inclusive
//returns Second Minimum ie. smallest loser (second min) to winner (min)
int*Second_Minimum(int*L,int p,int r){
    int*winner=nullptr;
    stack<int*>post_order;
    int*second_minimum=Find_Candidates(L,p,r,winner,post_order);
    print_in_order(post_order,0);
    return second_minimum; 
}

//post_order is solely for printing purpose
//returns pointer to second minimum or nullptr if it doesn't exist
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order){
    //a single element must be winner
    if(p==r){
        winner=L+p; 
        post_order.push(nullptr);//left child
        post_order.push(nullptr);//right child
        post_order.push(winner);//this node
        return nullptr;//no one lost to the winner 
    }
    int q=(p+r)/2; //same as floor((p+r)/2), aka lower median
    int*lt_smallest_loser=Find_Candidates(L,p,q,winner,post_order); //smallest loser to winner in left subtree
    int*lt_winner=winner; //winner from left subtree 
    int*rt_smallest_loser=Find_Candidates(L,q+1,r,winner,post_order); //smallest loser to winner in right subtree
    int*rt_winner=winner; //winner from right subtree 

    if(*lt_winner<*rt_winner){
        winner=lt_winner;//rt_winner becomes a loser now 
        post_order.push(winner);
        if(lt_smallest_loser!=nullptr&&
            *lt_smallest_loser<*rt_winner){
            return lt_smallest_loser;// still the smallest loser 
        }else
            return rt_winner;// rt_winner becomes the smallest loser 
    }else{
        winner=rt_winner;//lt_winner becomes a loser now 
        post_order.push(winner);
        if(rt_smallest_loser!=nullptr&&
            *rt_smallest_loser<*lt_winner){
            return rt_smallest_loser;// still the smallest loser 
        }else
            return lt_winner;// lt_winner becomes the smallest loser 
    }
}

void print_in_order(stack<int*>&post_order,int depth){
    int*root=post_order.top(); 
    post_order.pop();
    if(root==nullptr)
        return; 
    else{
        //print right
        print_in_order(post_order,depth+1);
        for(int i=0;i<depth;++i)
            cout<<'\t';//print tab
        cout<<*root<<endl;
        //print left
        print_in_order(post_order,depth+1);
    }
}

int main(){
    int L[]{3,1,5,2,4};
    int n=sizeof(L)/sizeof(int);
    int*result=Second_Minimum(L,0,n-1); 
    cout<<"2nd smallest: "; 
    if(result!=nullptr)
        cout<<*result<<endl;
    else
        cout<<"doesn't exist"<<endl;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.