Find second min number .

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
peterlin
New poster
Posts: 5
Joined: Wed Dec 18, 2002 4:46 pm

Find second min number .

Post by peterlin »

I know we can find min number in n-1
but how can we find the second min number in n + lg(n) -2

It is a question in Introduce to Algorithm (9.1-1)

Did anyone have idea of this ?

Best wishes,
Peter

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

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 ???
ImageWe are all in a circular way, no advances, only moving and moving!

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Re: Find second min number .

Post by arnsfelt »

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 ?

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Re: Find second min number .

Post by Moni »

arnsfelt 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 ?
Could you please explain it in details :(
ImageWe are all in a circular way, no advances, only moving and moving!

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

Hi Moni,

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];
}

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

Re: Find second min number .

Post by Lars Hellsten »

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 n-1 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 k-th smallest element in an array in O(n) time.

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

Welcome! Bugz! in uva forum!

I knew that but about the problems with those complexity and that "Tournament method" with the tree and it's child.........

Thanks to Lars for his little briefing......... ;)
ImageWe are all in a circular way, no advances, only moving and moving!

matt80
New poster
Posts: 6
Joined: Thu May 01, 2003 9:49 am

Re: Find second min number .

Post by matt80 »

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 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:

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

matt80
New poster
Posts: 6
Joined: Thu May 01, 2003 9:49 am

Re: Find second min number .

Post by matt80 »

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. :oops:
Now I can see your solution doesn't need so much memory.
Therefore mine is just a version of the bugzpodder's algorithm.:oops:
Mattia

Fernandez Jose
New poster
Posts: 8
Joined: Wed Sep 18, 2002 2:10 am

Re: Find second min number .

Post by Fernandez Jose »

[quote="peterlin"]I know we can find min number in n-1
but how can we find the second min number in n + lg(n) -2

It is a question in Introduce to Algorithm (9.1-1)

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.

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

question about the tournament algo

Post by zsepi »

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 re-edited 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.

Post Reply

Return to “Algorithms”