The third largest number in an array?

Question

1.00/5 (2 votes)

See more:

C#

can you tell me how to find third largest number in an array?
without ordering
thanks for answers

Posted 22-Apr-12 4:54am

Amir-Mar2012

Updated 21-Jan-21 3:14am

Add a Solution

3 solutions

Solution 3

If you can't order the array for whatever reasons, you can always create an additional index that will just reflect the order, and then use this index to locate the needed element.

Posted 10-Jun-12 8:17am

Vitaly Tomilov

Solution 2

//Take three variable and assign first element of the array and then
check for the largest no. If found then shift the first no to second variable and so in third variable.

C#

int[] arr = {1,8,4,5,12,2,5,6,7,1,90,100,56,8,34};

            int temp, f, s, t;
            f = s = t = arr[0];
            foreach (int i in arr)
            {
                if (f < i)
                {
                    temp = f;
                    f = i;
                    s = temp;
                }
                if (s < i && f > i)
                {
                    temp = i;
                    s = i;
                    t = temp;
                }
                if (t < i && s > i)
                {
                    temp = i;
                     t=i;
                }
            }
            MessageBox.Show(t.ToString());

Posted 9-Jun-12 8:48am

Aamresh Kumar

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2012-04-22T04:58:00

Solution 1

Personally, I would order them: sorted into descending order would make it a trivial problem.
But if you aren't allowed to use sorting, then it's homework. So you don't get code!

But it's not complex.
Think about it: how would you find the maximum value?
Answer: Loop though all entries in the array comparing each against the current value. If this value is larger than current it becomes the new maximum.

It's a pretty simple matter to make this find the top three: when you replace the maximum, move it into the second largest, and the second into the third. One pass, done.

Posted 22-Apr-12 4:58am

OriginalGriff

Comments

VJ Reddy 22-Apr-12 11:12am

Good suggestion. 5!

nv3 23-Apr-12 14:21pm

Hi OriginalGriff.

With all my sympathy for your solution, I think it is not entirely correct. The single loop for finding the maximum works fine of course; but the generalization for the top three is a bit tricky. Consider the following sequence:

1 5 10 7 6

When arriving at the 10 the top-three array would contain (10, 5, 1). When encountering the 7 you throw it away, as it is not larger than the current maximum. Same with 6. So your algorithm would result in 10, 5, 1 being the top three.

So you actually have to compare each new element against all members in the top-three array or until you find one that is smaller.

OriginalGriff 23-Apr-12 14:47pm

Good point! That's partly why I would sort them first...
Well spotted - I'd give you 5 if I could. So I found one of your answers, and did... :)

nv3 23-Apr-12 15:16pm

That was very kind of you, thank you! Actually, this algorithm would take almost 3N comparisons, while a good sorting algorithm would only take slightly more (in the order of N ln N). Hence your feeling was right, that doing a sort is not the worst idea in the world.

I wonder whether there is an algorithm that does much better than 3N to find the top three. If I find anything substantial, I will get back to you folks.

OriginalGriff 23-Apr-12 15:22pm

The big advantage of doing the sort is that it reduces testing - if this isn't a time critical code section, then I would go with the sort version purely on development time!

nv3 23-Apr-12 16:44pm

I absolutely agree. That's what I would do as well.

Just for the sake of coming up with a solution that does not use a regular sort, here is what I would do:

We use a stack out of three cells to store our top-three candidates that we have found so far. Let's call them A, B and C, with C being the lowest value. Now loop over the array and compare every new element X at first with C, our lowest of the top-three. If it's larger, replace C with X. Then compare it with B. If it's larger push B down into C and set B to X. Then repeat that for A.

In this way, in many cases we will get away with just one comparison, namely X to C. This is because after some time, relatively large values will have accrued in A, B, C and so most elements that we compare will be lower than C.

This is more economical than starting the comparison with X to A, then B and finally C.

All that said, this is nothing else than doing a good old Insertion Sort, except that we throw everything away below the top-three elements.

I hope this info comes in time for Amir-Mar2012.