Second Highest number in an array

[Jaspreet]

I was working on some database application and had this small task of
getting the second highes marks in a class. I was able to do that using
subqueries.

Just thinking what is a good way of getting second highest value in an
integer array. One method I know of is to make the 1st pass through the
array and find the highest number. In the second pass we can find the
highest number which is less than the number we obtained in the 1st
pass.

However there has to be a better and more efficient way of doing this.
Please just let me know some hints and I would try it on my own in C.

Thanks and have an enjoyable weekend.

[Anonymous 7843]

Re: Second Highest number in an array

In article <1127512846.156 447.263710@g43g 2000cwa.googleg roups.com>,
Jaspreet <jsingh.oberoi@ gmail.com> wrote:[color=blue]
>
> Just thinking what is a good way of getting second highest value in an
> integer array. One method I know of is to make the 1st pass through the
> array and find the highest number. In the second pass we can find the
> highest number which is less than the number we obtained in the 1st
> pass.
>
> However there has to be a better and more efficient way of doing this.
> Please just let me know some hints and I would try it on my own in C.[/color]

Just make one pass through the array. Keep two variables,
which track:

* highest so far
* 2nd highest so far

As you iterate through the array, when you find a new "highest"
one, move the previous "highest" to "2nd highest." Plus, if
you happen upon an element that his higher than the 2nd highest
but not as high as the first, make that the 2nd highest without
disturbing the highest.

As you extend the idea to finding (for example) 490th highest
element it becomes quite a bit less efficient, since it's
basically an insertion sort. At some point it's better to
just sort the array and then everything is positioned perfectly.

[Patrick M.]

Re: Second Highest number in an array

Jaspreet wrote:[color=blue]
> I was working on some database application and had this small task of
> getting the second highes marks in a class. I was able to do that using
> subqueries.
>
> Just thinking what is a good way of getting second highest value in an
> integer array. One method I know of is to make the 1st pass through the
> array and find the highest number. In the second pass we can find the
> highest number which is less than the number we obtained in the 1st
> pass.
>
> However there has to be a better and more efficient way of doing this.
> Please just let me know some hints and I would try it on my own in C.
>
> Thanks and have an enjoyable weekend.
>[/color]

Well, it may not be the _most_ efficient, but it's more efficient than
the way you're thinking of. What you could do is make a copy array (you
don't even need to, unless you don't want to edit the original array,
and since it's a database application you probably don't) of the
original array, pass through it once, sorting it from highest to lowest.
Then, the highest value of the array will be in array[0], and the
second highest value in the array will be in array[1].

--
Patrick M.
/* EOF */

[Alexei A. Frounze]

Re: Second Highest number in an array

"Jaspreet" <jsingh.oberoi@ gmail.com> wrote in message
news:1127512846 .156447.263710@ g43g2000cwa.goo glegroups.com.. .[color=blue]
> Just thinking what is a good way of getting second highest value in an
> integer array. One method I know of is to make the 1st pass through the
> array and find the highest number. In the second pass we can find the
> highest number which is less than the number we obtained in the 1st
> pass.
>
> However there has to be a better and more efficient way of doing this.
> Please just let me know some hints and I would try it on my own in C.[/color]

This is OT since it has nothing to do with C. It's just an algorithm, which
is a language independent thing.

Hint anyway: instead of having 2 passes and 1 running variable in each of
them you may have 1 pass and 2 running vars (highest & 2nd highest) in it.

Alex

[Christian Bau]

Re: Second Highest number in an array

In article <1127512846.156 447.263710@g43g 2000cwa.googleg roups.com>,
"Jaspreet" <jsingh.oberoi@ gmail.com> wrote:
[color=blue]
> I was working on some database application and had this small task of
> getting the second highes marks in a class. I was able to do that using
> subqueries.
>
> Just thinking what is a good way of getting second highest value in an
> integer array. One method I know of is to make the 1st pass through the
> array and find the highest number. In the second pass we can find the
> highest number which is less than the number we obtained in the 1st
> pass.
>
> However there has to be a better and more efficient way of doing this.
> Please just let me know some hints and I would try it on my own in C.[/color]

Loop through the array once. Keep track of the largest and second largest
element found so far. You can ignore everything that is smallest than
the second largest object found so far.

[Christian Kandeler]

Re: Second Highest number in an array

Patrick M. wrote:
[color=blue]
> Well, it may not be the _most_ efficient, but it's more efficient than
> the way you're thinking of. What you could do is make a copy array (you
> don't even need to, unless you don't want to edit the original array,
> and since it's a database application you probably don't) of the
> original array, pass through it once, sorting it from highest to lowest.
> Then, the highest value of the array will be in array[0], and the
> second highest value in the array will be in array[1].[/color]

Please show us the O(n) sorting algorithm you use for that.


Christian

[Nils O. Selåsdal]

Re: Second Highest number in an array

Jaspreet wrote:[color=blue]
> I was working on some database application and had this small task of
> getting the second highes marks in a class. I was able to do that using
> subqueries.
>
> Just thinking what is a good way of getting second highest value in an
> integer array. One method I know of is to make the 1st pass through the
> array and find the highest number. In the second pass we can find the
> highest number which is less than the number we obtained in the 1st
> pass.
>
> However there has to be a better and more efficient way of doing this.
> Please just let me know some hints and I would try it on my own in C.[/color]
If you keep it sorted while you build your array, you can do e.g.
a binary search on the array.
Also consider reading about binary trees.

[Jaspreet]

Re: Second Highest number in an array

Nils O. Selåsdal wrote:[color=blue]
> Jaspreet wrote:[color=green]
> > I was working on some database application and had this small task of
> > getting the second highes marks in a class. I was able to do that using
> > subqueries.
> >
> > Just thinking what is a good way of getting second highest value in an
> > integer array. One method I know of is to make the 1st pass through the
> > array and find the highest number. In the second pass we can find the
> > highest number which is less than the number we obtained in the 1st
> > pass.
> >
> > However there has to be a better and more efficient way of doing this.
> > Please just let me know some hints and I would try it on my own in C.[/color]
> If you keep it sorted while you build your array, you can do e.g.
> a binary search on the array.
> Also consider reading about binary trees.[/color]

Hi

Thanks a lot guys. Yes it seems it would have been better if I had some
foresight and had maintained the array in the sorted order.

Thanks once again.

[websnarf@gmail.com]

Re: Second Highest number in an array

Anonymous 7843 wrote:[color=blue]
> Jaspreet <jsingh.oberoi@ gmail.com> wrote:[color=green]
> > Just thinking what is a good way of getting second highest value in an
> > integer array. One method I know of is to make the 1st pass through the
> > array and find the highest number. In the second pass we can find the
> > highest number which is less than the number we obtained in the 1st
> > pass.
> >
> > However there has to be a better and more efficient way of doing this.
> > Please just let me know some hints and I would try it on my own in C.[/color]
>
> Just make one pass through the array. Keep two variables,
> which track:
>
> * highest so far
> * 2nd highest so far
>
> As you iterate through the array, when you find a new "highest"
> one, move the previous "highest" to "2nd highest." Plus, if
> you happen upon an element that his higher than the 2nd highest
> but not as high as the first, make that the 2nd highest without
> disturbing the highest.[/color]

For specifically the second highest, I will endorse this algorithm.
You are hardly going to do better.
[color=blue]
> As you extend the idea to finding (for example) 490th highest
> element it becomes quite a bit less efficient, since it's
> basically an insertion sort.[/color]

Well, for the mth highest this algorithm is basically O(m^2*n).
However, there exists an O(n) "kth rank" algorithm. See:

http://www.nist.gov/dads/HTML/select.html

http://en.wikipedia.org/wiki/Selection_algorithm

Unfortunately, I have not seen a really good explanation for why the
implementation truly matches the analysis. However, if you think about
it, its not hard to see that they are right. The "group of 5" are not
adjacent sub-elements, but in fact seperated by n/5 offsets, and then
each group is just shifted down one element at a time, with some number
of tail entries with only 4 elements each. In this way, the median of
5 steps are O(n) and the final partitioning does not require additional
movement operations.
[color=blue]
> At some point it's better to just sort the array and then everything is
> positioned perfectly.[/color]

Well, O(n) < O(n*ln(n)), so sorting is only going to be better if you
have many "kth element requests" relative to the number of insert or
delete operations.

--
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sf.net/

[Joe Wright]

Re: Second Highest number in an array

Jaspreet wrote:[color=blue]
> I was working on some database application and had this small task of
> getting the second highes marks in a class. I was able to do that using
> subqueries.
>
> Just thinking what is a good way of getting second highest value in an
> integer array. One method I know of is to make the 1st pass through the
> array and find the highest number. In the second pass we can find the
> highest number which is less than the number we obtained in the 1st
> pass.
>
> However there has to be a better and more efficient way of doing this.
> Please just let me know some hints and I would try it on my own in C.
>
> Thanks and have an enjoyable weekend.
>[/color]

#include <stdio.h>
int main(void) {
int pri, sec, i, v;
int arr[] = {4,10,3,8,6,7,2 ,7,9,2,0};
pri = sec = 0;
for (i = 0; arr[i]; ++i) {
v = arr[i];
if (v > pri) sec = pri, pri = v;
if (v > sec && v < pri) sec = v;
}
printf("pri is %d, sec is %d\n", pri, sec);
return 0;
}

One trip through the array.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Mara Guida]

Re: Second Highest number in an array

Joe Wright wrote:[color=blue]
> #include <stdio.h>
> int main(void) {
> int pri, sec, i, v;[/color]

int arr[] = {-4,-10,-3,-8,-6,-7,-2,-7,-9,-2,0}; /* Ah! Ah! */
[color=blue]
> pri = sec = 0;
> for (i = 0; arr[i]; ++i) {
> v = arr[i];
> if (v > pri) sec = pri, pri = v;
> if (v > sec && v < pri) sec = v;
> }
> printf("pri is %d, sec is %d\n", pri, sec);
> return 0;
> }[/color]

[CBFalconer]

Re: Second Highest number in an array

Joe Wright wrote:[color=blue]
> Jaspreet wrote:
>[color=green]
>> I was working on some database application and had this small
>> task of getting the second highes marks in a class. I was able
>> to do that using subqueries.
>>
>> Just thinking what is a good way of getting second highest
>> value in an integer array. One method I know of is to make the
>> 1st pass through the array and find the highest number. In the
>> second pass we can find the highest number which is less than
>> the number we obtained in the 1st pass.
>>
>> However there has to be a better and more efficient way of
>> doing this. Please just let me know some hints and I would try
>> it on my own in C.[/color]
>
> #include <stdio.h>
> int main(void) {
> int pri, sec, i, v;
> int arr[] = {4,10,3,8,6,7,2 ,7,9,2,0};
> pri = sec = 0;
> for (i = 0; arr[i]; ++i) {
> v = arr[i];
> if (v > pri) sec = pri, pri = v;
> if (v > sec && v < pri) sec = v;
> }
> printf("pri is %d, sec is %d\n", pri, sec);
> return 0;
> }
>
> One trip through the array.[/color]

On the principle of "look to the innermost loop", why the extra
test?

for (i = 0, v = arr[0]; v; v = arr[++i])
if (v > pri) {sec = pri; pri = v;}
else if (v > sec) sec = v;

and we can do even better with a pointer.

int *p;
...
for (p = arr, v = *p++; v; v = *p++)
... same ...

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

[Joe Wright]

Re: Second Highest number in an array

CBFalconer wrote:[color=blue]
> Joe Wright wrote:
>[color=green]
>>Jaspreet wrote:
>>
>>[color=darkred]
>>>I was working on some database application and had this small
>>>task of getting the second highes marks in a class. I was able
>>>to do that using subqueries.
>>>
>>>Just thinking what is a good way of getting second highest
>>>value in an integer array. One method I know of is to make the
>>>1st pass through the array and find the highest number. In the
>>>second pass we can find the highest number which is less than
>>>the number we obtained in the 1st pass.
>>>
>>>However there has to be a better and more efficient way of
>>>doing this. Please just let me know some hints and I would try
>>>it on my own in C.[/color]
>>
>>#include <stdio.h>
>>int main(void) {
>> int pri, sec, i, v;
>> int arr[] = {4,10,3,8,6,7,2 ,7,9,2,0};
>> pri = sec = 0;
>> for (i = 0; arr[i]; ++i) {
>> v = arr[i];
>> if (v > pri) sec = pri, pri = v;
>> if (v > sec && v < pri) sec = v;
>> }
>> printf("pri is %d, sec is %d\n", pri, sec);
>> return 0;
>>}
>>
>>One trip through the array.[/color]
>
>
> On the principle of "look to the innermost loop", why the extra
> test?
>
> for (i = 0, v = arr[0]; v; v = arr[++i])
> if (v > pri) {sec = pri; pri = v;}
> else if (v > sec) sec = v;
>
> and we can do even better with a pointer.
>
> int *p;
> ...
> for (p = arr, v = *p++; v; v = *p++)
> ... same ...
>[/color]
I take your first argument. The for () can be simpler. Cute block.

for (i = 0; (v = arr[i]); ++i) {
if (v > pri) sec = pri, pri = v;
else if (v > sec) sec = v;
}

The pointer treatment can be simpler too..

for (p = arr; (v = *p++);)
... same ...

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Thad Smith]

Re: Second Highest number in an array

CBFalconer wrote:[color=blue]
>
> Joe Wright wrote:[color=green]
> > Jaspreet wrote:
> >[color=darkred]
> >> Just thinking what is a good way of getting second highest
> >> value in an integer array.[/color][/color][/color]
....[color=blue][color=green][color=darkred]
> >> However there has to be a better and more efficient way of
> >> doing this. Please just let me know some hints and I would try
> >> it on my own in C.[/color]
> >
> > #include <stdio.h>
> > int main(void) {
> > int pri, sec, i, v;
> > int arr[] = {4,10,3,8,6,7,2 ,7,9,2,0};
> > pri = sec = 0;
> > for (i = 0; arr[i]; ++i) {
> > v = arr[i];
> > if (v > pri) sec = pri, pri = v;
> > if (v > sec && v < pri) sec = v;
> > }
> > printf("pri is %d, sec is %d\n", pri, sec);
> > return 0;
> > }[/color][/color]

If zero termination of the array is not specified, the loop control is
incorrect. The correct termination is

for (i=0; i < sizeof arr/sizeof *arr; i++)

I usually define a macro
#define DIM(a) (sizeof(a)/sizeof(a[0]))
for such use.

Note, in general, it is more robust to terminate a list on something
other than a special data value.

As someone else pointed out, this fails for all negative numbers,
since the initial value is larger than array values. In general, you
need a separate indication that no value has been found. You can a
maximum negative value as a place holder if you constrain the data to
not include the maximum negative value.
[color=blue]
> On the principle of "look to the innermost loop", why the extra
> test?
>
> for (i = 0, v = arr[0]; v; v = arr[++i])
> if (v > pri) {sec = pri; pri = v;}
> else if (v > sec) sec = v;[/color]


The replacement code is functionally different. It returns the value
of the element in the second position when ordered by descending value
and allowing duplicates, whereas the first version returns the second
highest value when each value is only represented once.

My interpretation of the literal definition of "second highest value"
would be the latter, based on "second highest" never being the same as
"highest". This is often not the colloquial meaning of second
highest, but I would prefer literal interpretation here, unless
specified otherwise.

--
Thad

[RSoIsCaIrLiIoA]

Re: Second Highest number in an array

On Fri, 27 Jan 2006 -0500, CBFalconer <cbfalconer@yah oo.com> wrote:[color=blue]
>Joe Wright wrote:[color=green]
>> Jaspreet wrote:[color=darkred]
>>> I was working on some database application and had this small
>>> task of getting the second highes marks in a class. I was able
>>> to do that using subqueries.
>>>
>>> Just thinking what is a good way of getting second highest
>>> value in an integer array. One method I know of is to make the
>>> 1st pass through the array and find the highest number. In the
>>> second pass we can find the highest number which is less than
>>> the number we obtained in the 1st pass.
>>>
>>> However there has to be a better and more efficient way of
>>> doing this. Please just let me know some hints and I would try
>>> it on my own in C.[/color]
>>
>> #include <stdio.h>
>> int main(void) {
>> int pri, sec, i, v;
>> int arr[] = {4,10,3,8,6,7,2 ,7,9,2,0};
>> pri = sec = 0;
>> for (i = 0; arr[i]; ++i) {
>> v = arr[i];
>> if (v > pri) sec = pri, pri = v;
>> if (v > sec && v < pri) sec = v;
>> }
>> printf("pri is %d, sec is %d\n", pri, sec);
>> return 0;
>> }
>>
>> One trip through the array.[/color]
>
>On the principle of "look to the innermost loop", why the extra
>test?
>
> for (i = 0, v = arr[0]; v; v = arr[++i])
> if (v > pri) {sec = pri; pri = v;}
> else if (v > sec) sec = v;
>
>and we can do even better with a pointer.
>
> int *p;
> ...
> for (p = arr, v = *p++; v; v = *p++)
> ... same ...[/color]

//////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>

int primi2(int*, int*, int*, unsigned);

int main(void)
{int pri=0, sec=0, r, v, size;
int arr[] = {4,-10,3,8,6,7,2,7,-9,2,-5000}, arr1[]={1};
////////////////////////////////////
size=sizeof arr1/ sizeof(int);
r=primi2(&pri, &sec, arr1, size);
if(r==0) printf("array empy\n");
else if(r==1)
printf("solo un elemento pri=%d sec==%d\n", pri, sec);
else printf("pri is %d, sec is %d\n", pri, sec);
return 0;
}
////////////////////////////////////

; nasmw -fobj rog.asm

section _DATA public align=4 class=DATA use32

global _primi2

section _TEXT public align=1 class=CODE use32


; s= 0r, 4c, 8b, 12Ra, 16@p1, 20@p2, 24@arr, 28@size
_primi2:
push ebx
push ecx
push edx
%define @p1 esp+16
%define @p2 esp+20
%define @arr esp+24
%define @size esp+28
mov eax, [@arr]
mov ecx, [@size]
cmp ecx, 0
jne .l0
mov eax, 0
jmp short .fi
..l0:
mov ebx, [eax]
dec ecx
jnz .l1
mov eax, [@p1]
mov ecx, [@p2]
mov [eax], ebx
mov [ecx], ebx
mov eax, 1
jmp short .fi

..l1:
add eax, 4
cmp [eax], ebx
jle .l2
mov edx, ebx
mov ebx, [eax]
jmp short .m0
..l2:
mov edx, [eax]
..m0:
dec ecx
jnz .l3
..c0:
mov eax, [@p1]
mov ecx, [@p2]
mov [eax], ebx
mov [ecx], edx
mov eax, 2
jmp short .fi

..l3:
add eax, 4
cmp [eax], edx
jle .l5
cmp [eax], ebx
jle .l4
mov edx, ebx
mov ebx, [eax]
jmp short .l5
..l4:
mov edx, [eax]
..l5:
dec ecx
jnz .l3

jmp short .c0
..fi:
%undef @p1
%undef @p2
%undef @arr
%undef @size
pop edx
pop ecx
pop ebx
ret