Click here to Skip to main content
15,031,680 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
can you tell me how to find third largest number in an array?
without ordering
thanks for answers
Posted
Updated 21-Jan-21 3:14am

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.
   
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.
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.
   
//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());
   

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




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900