440,230 Members | 2,471 Online
Need help? Post your question and get tips & solutions from a community of 440,230 IT Pros & Developers. It's quick & easy.

# Second Highest number in an array

 P: n/a 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. Nov 15 '05 #1
21 Replies

 P: n/a In article <11**********************@g43g2000cwa.googlegroups .com>, Jaspreet wrote: 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. 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. Nov 15 '05 #2

 P: n/a 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. Thanks and have an enjoyable weekend. 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 */ Nov 15 '05 #3

 P: n/a "Jaspreet" wrote in message news:11**********************@g43g2000cwa.googlegr oups.com... 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. 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 Nov 15 '05 #4

 P: n/a In article <11**********************@g43g2000cwa.googlegroups .com>, "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. 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. Nov 15 '05 #5

 P: n/a Patrick M. wrote: 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]. Please show us the O(n) sorting algorithm you use for that. Christian Nov 15 '05 #6

 P: n/a 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. 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. Nov 15 '05 #7

 P: n/a Nils O. Selåsdal 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. 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. 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. Nov 15 '05 #8

 P: n/a Anonymous 7843 wrote: Jaspreet wrote: 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. 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. For specifically the second highest, I will endorse this algorithm. You are hardly going to do better. 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. 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. At some point it's better to just sort the array and then everything is positioned perfectly. 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/ Nov 15 '05 #9

 P: n/a 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. Thanks and have an enjoyable weekend. #include 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 --- Jan 28 '06 #10

 P: n/a Joe Wright wrote: #include 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; } Jan 28 '06 #11

 P: n/a 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 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 Jan 28 '06 #12

 P: n/a CBFalconer wrote: Joe Wright wrote:Jaspreet wrote:I was working on some database application and had this smalltask of getting the second highes marks in a class. I was ableto do that using subqueries.Just thinking what is a good way of getting second highestvalue in an integer array. One method I know of is to make the1st pass through the array and find the highest number. In thesecond pass we can find the highest number which is less thanthe number we obtained in the 1st pass.However there has to be a better and more efficient way ofdoing this. Please just let me know some hints and I would tryit on my own in C.#include 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 --- Jan 28 '06 #13

 P: n/a 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 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. -- Thad Jan 28 '06 #14

 P: n/a On Fri, 27 Jan 2006 -0500, 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 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 extratest? 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 #include 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 Jan 31 '06 #15

 P: n/a RSoIsCaIrLiIoA wrote: ////////////////////////////////////// Don't use `//`, at least not in the posts. #include #include 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: Please stay remotely on-topic, and your posts would also greatly benefit from at least some descriptive text. Cheers Vladimir Jan 31 '06 #16

 P: n/a Vladimir S. Oka wrote: RSoIsCaIrLiIoA wrote: ////////////////////////////////////// Don't use `//`, at least not in the posts. #include #include int primi2(int*, int*, int*, unsigned); You may have wanted to `extern` this. 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. Jan 31 '06 #17

 P: n/a Flash Gordon wrote: Vladimir S. Oka wrote: RSoIsCaIrLiIoA wrote: ////////////////////////////////////// Don't use `//`, at least not in the posts. #include #include int primi2(int*, int*, int*, unsigned); You may have wanted to `extern` this. 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 Vladimir -- If they can make penicillin out of moldy bread, they can sure make something out of you. -- Muhammad Ali Jan 31 '06 #18

 P: n/a On 31 Jan 2006 05:07:08 -0800, "Vladimir S. Oka" 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 #include 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: 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: 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 Jan 31 '06 #19

 P: n/a On Tue, 31 Jan 2006 23:34:00 +0100, in comp.lang.c , RSoIsCaIrLiIoA wrote: On 31 Jan 2006 05:07:08 -0800, "Vladimir S. Oka" 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? // because wrapped comment lines will not be comments any more, and because some broken mail clients interpret // as being part of a url. Mark McIntyre -- "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." --Brian Kernighan ----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =---- Feb 1 '06 #20

 P: n/a RSoIsCaIrLiIoA writes: On 31 Jan 2006 05:07:08 -0800, "Vladimir S. Oka" 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? Because they're not supported by all compilers, and because long "//" comments are often line-wrapped, creating syntax errors even for compilers that support them. [snip] 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 [68 lines deleted] Why do you keep posting assembly language to comp.lang.c? An assembly listing generated by a C compiler *might* be topical in some rare circumstances, but this appears to be hand-written. I'm sure there's a newsgroup where assembly language for whatever CPU you're using (x86?) might be topical. This isn't it. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Feb 1 '06 #21

 P: n/a "Vladimir S. Oka" wrote: 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 ... Please stay remotely on-topic, and your posts would also greatly 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 Feb 1 '06 #22

### This discussion thread is closed

Replies have been disabled for this discussion.