Find second min number .
Moderator: Board moderators
Find second min number .
I know we can find min number in n1
but how can we find the second min number in n + lg(n) 2
It is a question in Introduce to Algorithm (9.11)
Did anyone have idea of this ?
Best wishes,
Peter
but how can we find the second min number in n + lg(n) 2
It is a question in Introduce to Algorithm (9.11)
Did anyone have idea of this ?
Best wishes,
Peter

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
I am not sure but I think you can use a array of size 2;
And when going through the data as you used for the min value lookin for the next smallest and now do the same but keep them in that 2 sized array. Here you have to check the two values only for finding the 2nd min........
Is that you asked for ???
And when going through the data as you used for the min value lookin for the next smallest and now do the same but keep them in that 2 sized array. Here you have to check the two values only for finding the 2nd min........
Is that you asked for ???
We are all in a circular way, no advances, only moving and moving!
Re: Find second min number .
The tournament method.
Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?
Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
Re: Find second min number .
Could you please explain it in detailsarnsfelt wrote:The tournament method.
Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?
We are all in a circular way, no advances, only moving and moving!

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
Hi Moni,
cant you just keep track of the two smallest numbers you find? like this:
cant you just keep track of the two smallest numbers you find? like this:
Code: Select all
for (i=0;i<n;i++){
if (arr[i]<num1) {num2=num1;num1=arr[i];}
else if (arr[i]<num2) num2=arr[i];
}

 New poster
 Posts: 20
 Joined: Thu Apr 10, 2003 10:53 pm
Re: Find second min number .
You can't just go through linearly and keep track of the 2 smallest because that can use 2n  3 comparisons in the worst case.
The tournament method works like this. First, assume n is a power of 2. Split all the elements up into arbitrary pairs. Do a comparison on each of the n/2 pairs, and then take the "winners" of each pair. Repeat until you have an overall winner (the smallest element). This requires n1 comparisons, and there are exactly lg(n) rounds. Also, for each element, keep a list of which numbers it beats.
Now, the second smallest must have been beaten by the smallest. So just scan through the list of elements beaten by the smallest, and find the minimum value in this list. The list has lg(n) elements, so this takes lg(n)  1 comparisons. Therefore, the total # of comparisons is always n  1 + lg(n)  1 = n + lg(n)  2 ccomparisons.
On a somewhat related note, CLR also describes how to find the kth smallest element in an array in O(n) time.
The tournament method works like this. First, assume n is a power of 2. Split all the elements up into arbitrary pairs. Do a comparison on each of the n/2 pairs, and then take the "winners" of each pair. Repeat until you have an overall winner (the smallest element). This requires n1 comparisons, and there are exactly lg(n) rounds. Also, for each element, keep a list of which numbers it beats.
Now, the second smallest must have been beaten by the smallest. So just scan through the list of elements beaten by the smallest, and find the minimum value in this list. The list has lg(n) elements, so this takes lg(n)  1 comparisons. Therefore, the total # of comparisons is always n  1 + lg(n)  1 = n + lg(n)  2 ccomparisons.
On a somewhat related note, CLR also describes how to find the kth smallest element in an array in O(n) time.
Re: Find second min number .
This is an intreasting solution but I think it is not a good idea. It could be fast but it waste a lot of memory. To list all elements that are beaten by each number took n*n/2 elements! This mean that you'll get out of memory very soon (about on 100000 elements).Lars Hellsten wrote: Now, the second smallest must have been beaten by the smallest. So just scan through the list of elements beaten by the smallest, and find the minimum value in this list. The list has lg(n) elements, so this takes lg(n)  1 comparisons. Therefore, the total # of comparisons is always n  1 + lg(n)  1 = n + lg(n)  2 ccomparisons.
This is my idea:
use an binary tree. Don't care about elements that should stay on the right of root and cut the root every time the length reach 3.
The second minimun number is the final root.
i.e.
8 6 9 4 5
' ' 8
' /
6
9 should be at the right of 8 so don't care about it
' ' ' 8
' ' /
' 6
' /
4
cut 8, so 6 becomes the new root
' ' 6
' /
4
5 should be at the right of 4, so it will be swapped with 6 and becames the root
' ' 6
' /
4
' \
' ' 5
' ' 5
' /
4
At the end the number we are looking for is the root.
What do you think about it?
Mattia
Re: Find second min number .
matt80 wrote:
This is an intreasting solution but I think it is not a good idea. It could be fast but it waste a lot of memory. To list all elements that are beaten by each number took n*n/2 elements! This mean that you'll get out of memory very soon (about on 100000 elements).
This is my idea:
...
What do you think about it?
Mattia
Ok, I have misunderstood.
Now I can see your solution doesn't need so much memory.
Therefore mine is just a version of the bugzpodder's algorithm.
Mattia

 New poster
 Posts: 8
 Joined: Wed Sep 18, 2002 2:10 am
Re: Find second min number .
[quote="peterlin"]I know we can find min number in n1
but how can we find the second min number in n + lg(n) 2
It is a question in Introduce to Algorithm (9.11)
Did anyone have idea of this ?
Best wishes,
Peter[/quote]
Depending on the nature of the numbers, the problem can be solved with a cost in the order of O(n), if all de numbers belong to a range, and there is no one number missing in the range.
Another approach, a bit risky is to modify the Quick Sort working with the smallest numbers each time. At the risk of taking the smallest as the pivot.
but how can we find the second min number in n + lg(n) 2
It is a question in Introduce to Algorithm (9.11)
Did anyone have idea of this ?
Best wishes,
Peter[/quote]
Depending on the nature of the numbers, the problem can be solved with a cost in the order of O(n), if all de numbers belong to a range, and there is no one number missing in the range.
Another approach, a bit risky is to modify the Quick Sort working with the smallest numbers each time. At the risk of taking the smallest as the pivot.
question about the tournament algo
if I am using the tournament algo, what happens if I have repeated numbers, and during the random pairs comparison i might compare let's say, 2 (x) and 2 (y). then it will say that (if x > y comparison is used) the second 2 (y) beat the first 2 (x)  now assuming that all the other numbers are greater than 2, then the algo isn't going to give the right answer, or did i misunderstand something?
also, just an idea: is it possible to speed up the algo to finish in linear time (assuming that somehow we took care of the problem mentioned before) this way? (for all who read the post before I reedited it: I was at work, made the entry in a a hurry, sorry for writing that silly statement)
[c]int numbers[MX] = {n numbers };
int i = 0,
j = n  1;
while(j > 1) {
while(i < j) {
/* numbers always contains the smaller number */
if(numbers > numbers[j]) numbers = numbers[j];
i++;
j;
}
i = 0;
}[/c]
I haven't tested the code yet, you might need to make a j++; after the i = 0, but I hope the idea is clear  at the end, the smallest number is at numbers[0] and the second smallest is at numbers[1]
please, give feedback!
zsepi
also, just an idea: is it possible to speed up the algo to finish in linear time (assuming that somehow we took care of the problem mentioned before) this way? (for all who read the post before I reedited it: I was at work, made the entry in a a hurry, sorry for writing that silly statement)
[c]int numbers[MX] = {n numbers };
int i = 0,
j = n  1;
while(j > 1) {
while(i < j) {
/* numbers always contains the smaller number */
if(numbers > numbers[j]) numbers = numbers[j];
i++;
j;
}
i = 0;
}[/c]
I haven't tested the code yet, you might need to make a j++; after the i = 0, but I hope the idea is clear  at the end, the smallest number is at numbers[0] and the second smallest is at numbers[1]
please, give feedback!
zsepi
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.