Velocity Reviews > Second Highest number in an array

# Second Highest number in an array

Mara Guida
Guest
Posts: n/a

 01-28-2006
Joe Wright wrote:
> #include <stdio.h>
> int main(void) {
> int pri, sec, i, v;

int arr[] = {-4,-10,-3,-8,-6,-7,-2,-7,-9,-2,0}; /* Ah! Ah! */

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

CBFalconer
Guest
Posts: n/a

 01-28-2006
Joe Wright wrote:
> Jaspreet wrote:
>
>> 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.

>
> #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.

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
Guest
Posts: n/a

 01-28-2006
CBFalconer wrote:
> Joe Wright wrote:
>
>>Jaspreet wrote:
>>
>>
>>>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.

>>
>>#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.

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

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

Guest
Posts: n/a

 01-28-2006
CBFalconer wrote:
>
> Joe Wright wrote:
> > Jaspreet wrote:
> >
> >> Just thinking what is a good way of getting second highest
> >> value in an integer array.

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

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

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.

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

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.

--

RSoIsCaIrLiIoA
Guest
Posts: n/a

 01-31-2006
On Fri, 27 Jan 2006 -0500, CBFalconer <(E-Mail Removed)> wrote:
>Joe Wright wrote:
>> Jaspreet wrote:
>>> 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.

>>
>> #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.

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

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

Guest
Posts: n/a

 01-31-2006
RSoIsCaIrLiIoA wrote:
> //////////////////////////////////////

Don't use `//`, at least not in the posts.

> #include <stdio.h>
> #include <stdlib.h>
>
> int primi2(int*, int*, int*, unsigned);

You may have wanted to `extern` this.

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

Now, this is one of the most off-topic things I've seen for a while!
What makes you thing we want to see your assembly code?!

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

benefit from at least some descriptive text.

Cheers

Flash Gordon
Guest
Posts: n/a

 01-31-2006
> RSoIsCaIrLiIoA wrote:
>> //////////////////////////////////////

>
> Don't use `//`, at least not in the posts.
>
>> #include <stdio.h>
>> #include <stdlib.h>
>>
>> int primi2(int*, int*, int*, unsigned);

>
> You may have wanted to `extern` this.

<snip>

Why? Function declarations act as extern declarations unless you specify
static.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

Guest
Posts: n/a

 01-31-2006
Flash Gordon wrote:

>> RSoIsCaIrLiIoA wrote:
>>> //////////////////////////////////////

>>
>> Don't use `//`, at least not in the posts.
>>
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>>
>>> int primi2(int*, int*, int*, unsigned);

>>
>> You may have wanted to `extern` this.

>
> <snip>
>
> Why? Function declarations act as extern declarations unless you
> specify static.

Yes. I stand corrected. Thanks!

I wanted to say "you may want", as I tend to like things explicit.
Especially seeing primi2() is an assembly function.

Cheers

--
If they can make penicillin out of moldy bread, they can sure make
something out of you.

RSoIsCaIrLiIoA
Guest
Posts: n/a

 01-31-2006
On 31 Jan 2006 05:07:08 -0800, "Vladimir S. Oka"
<(E-Mail Removed)> wrote:

>RSoIsCaIrLiIoA wrote:
>> //////////////////////////////////////

>
>Don't use `//`, at least not in the posts.

why? Because it is not in the standard as line begin comment chars?
Then seems to me i have not to use "extern" for a function
declaration.

It is possible this below is better because it gets what op want

////////////////////////////////////
#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, 0, 0}, arr1[]={1};
////////////////////////////////////
size=sizeof arr/ sizeof(int);
r=primi2(&pri, &sec, arr, 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;
}

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:
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:
cmp [eax], edx
jle .l5
cmp [eax], ebx
jle .l4
mov edx, ebx
mov ebx, [eax]
jmp short .l5
..l4:
jz .l5
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

CBFalconer
Guest
Posts: n/a

 01-31-2006
> RSoIsCaIrLiIoA wrote:
>

.... lots of junk snipped ...
>
> Now, this is one of the most off-topic things I've seen for a while!
> What makes you thing we want to see your assembly code?!
>

.... more snippage ...
>
> <snipped loads of assembly cobblers>
>
> benefit from at least some descriptive text.

RSoIsCaIrLiIoA is a troll, who has been trolling elsewhere
recently. Just PLONK him and be done with it.

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