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

# What the fastest algorithm for find max/min in an array of integers?

 P: n/a I know, only simple one: #include int main() { int min=0,max=0,i,arr; for(i=0;i<12;i++) arr[i]=rand()%31-10; for(i=0;i<12;i++) printf("%d\t",arr[i]); printf("\n"); for(i=0;i<12;i++) { if(arr[max]arr[i]) min=i; } printf("\nmax is: %d\n",arr[max]); printf("\nmin is: %d\n",arr[min]); return 0; } Jun 27 '08 #1
19 Replies

 P: n/a In article , Eugeny Myunster I know, only simple one: You're not going to get it enormously faster. Unless you store the data in a special way (sorted for example), you're going to have to look at all the elements. Some small changes that might improve speed: - you can start the loop at 1 rather than zero. No point comparing arr against itself; - store the min and max values in variables, rather than doing an array reference to retrieve them each time; - calculate both in one loop through the array; - if it's less than the minimum, it won't be more than the maximum. Do you really need to make it faster? Profile your whole program to see if this is important. -- Richard -- :wq Jun 27 '08 #2

 P: n/a In article , Eugeny Myunster int main() { int min=0,max=0,i,arr; for(i=0;i<12;i++) arr[i]=rand()%31-10; for(i=0;i<12;i++) printf("%d\t",arr[i]); printf("\n"); for(i=0;i<12;i++) { if(arr[max]arr[i]) min=i; } printf("\nmax is: %d\n",arr[max]); printf("\nmin is: %d\n",arr[min]); return 0; } Quicksort the array, then grab the first (min) and last (max) values? -- Don Bruder - da****@sonic.net - If your "From:" address isn't on my whitelist, or the subject of the message doesn't contain the exact text "PopperAndShadow" somewhere, any message sent to this address will go in the garbage without my ever knowing it arrived. Sorry...

 P: n/a Don Bruder , Eugeny Myunster I know, only simple one: [snip] > Quicksort the array, then grab the first (min) and last (max) values? Um, no. Sorting the array is typically O(N*log N), whereas finding the min and max in a linear search is O(N). (A side note: I'm guessing that you mean qsort. Remember that the standard library routine qsort doesn't necessarily use the quicksort algorithm.) -- Keith Thompson (The_Other_Keith) Nokia "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Jun 27 '08 #4

 P: n/a In article <87************@kvetch.smov.org>, Keith Thompson Um, no. Sorting the array is typically O(N*log N), whereas findingthe min and max in a linear search is O(N). .... as is, perhaps surprisingly, finding the median. -- Richard -- :wq Jun 27 '08 #5

 P: n/a On Apr 24, 1:28*pm, Eugeny Myunster int main() { * * * * int min=0,max=0,i,arr; * * * * for(i=0;i<12;i++) * * * * * * * * arr[i]=rand()%31-10; * * * * for(i=0;i<12;i++) * * * * * * * * printf("%d\t",arr[i]); * * * * printf("\n"); * * * * * * * * for(i=0;i<12;i++) * * * * { * * * * * * * * if(arr[max]arr[i]) * * * * * * * * * * * * min=i; * * * * } * * * * printf("\nmax is: %d\n",arr[max]); * * * * * * * * * * printf("\nmin is: %d\n",arr[min]); * * * * * * return 0; }- Hide quoted text - - Show quoted text - I'm not sure why the post I sent from my news server account never arrived (I sent it hours ago). Here is a repost: #include /* "Introduction to Algorithms" Cormen, Leiserson, Rivest pp. 186,187 ISBN: 0-07-013143-0 Simultaneous min & max using only 3*N/2 comparisons Written by Dann Corbit 9/25/2007 Donated to the public domain */ #ifdef e_type_LONG_DOUBLE typedef long double e_type; #elif defined(e_type_DOUBLE) typedef double e_type; #elif defined(e_type_FLOAT) typedef float e_type; #elif defined(e_type_UNSIGNED_LONG_LONG) typedef unsigned long long e_type; #elif defined(e_type_LONG_LONG) typedef long long e_type; #elif defined(e_type_UNSIGNED_LONG) typedef unsigned long e_type; #elif defined(e_type_LONG) typedef long e_type; #elif defined(e_type_UNSIGNED) typedef unsigned e_type; #elif defined(e_type_INT) typedef int e_type; #elif defined(e_type_SHORT) typedef short e_type; #elif defined(e_type_UNSIGNED_SHORT) typedef unsigned e_type; #elif defined(e_type_CHAR) typedef char e_type; #elif defined(e_type_UNSIGNED_CHAR) typedef unsigned char e_type; #elif defined (__cplusplus) template < class e_type // works with stl string class etc... #endif void minmax( e_type * a, // input array size_t arr_size, // array length e_type * min_e, // smallest thing found e_type * max_e // biggest thing found ) { e_type min_et; e_type max_et; size_t i, n; if (arr_size % 2) { min_et = a; max_et = a; n = 1; } else { if (a a) { max_et = a; min_et = a; } else { min_et = a; max_et = a; } n = 2; } for (i = n; i < arr_size; i += 2) { if (a[i] a[i + 1]) { max_et = max_et a[i] ? max_et : a[i]; min_et = min_et < a[i + 1] ? min_et : a[i + 1]; } else { max_et = max_et a[i + 1] ? max_et : a[i + 1]; min_et = min_et < a[i] ? min_et : a[i]; } } *min_e = min_et; *max_e = max_et; } #if defined( UNIT_TEST ) && (defined (e_type_DOUBLE) || defined( __cplusplus)) #include char string; double foo; int main(void) { size_t i = 0; double dmin, dmax; while (fgets(string, sizeof string, stdin)) { foo[i++] = atof(string); if (i 32766) break; } minmax(foo, i, &dmin, &dmax); printf("min=%f, max=%f\n", dmin, dmax); return 0; } #endif /* C:\tmp>cl /W4 /Ox /DUNIT_TEST /De_type_DOUBLE minmax.c Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. minmax.c Microsoft (R) Incremental Linker Version 8.00.50727.762 Copyright (C) Microsoft Corporation. All rights reserved. /out:minmax.exe minmax.obj C:\tmp>dir n*.txt Volume in drive C has no label. Volume Serial Number is 0890-87CA Directory of C:\tmp 04/08/2008 04:13 PM 47,206,979 n.txt 1 File(s) 47,206,979 bytes 0 Dir(s) 4,932,272,128 bytes free C:\tmp>minmax < n.txt min=0.000043, max=20920.000000 */ Jun 27 '08 #6

 P: n/a It seems that this code can not improve the performance. because the comparison was not reduced. On Apr 25, 9:33 am, user923005 int main() { int min=0,max=0,i,arr; for(i=0;i<12;i++) arr[i]=rand()%31-10; for(i=0;i<12;i++) printf("%d\t",arr[i]); printf("\n"); for(i=0;i<12;i++) { if(arr[max]arr[i]) min=i; } printf("\nmax is: %d\n",arr[max]); printf("\nmin is: %d\n",arr[min]); return 0; }- Hide quoted text - - Show quoted text - I'm not sure why the post I sent from my news server account never arrived (I sent it hours ago). Here is a repost: #include /* "Introduction to Algorithms" Cormen, Leiserson, Rivest pp. 186,187 ISBN: 0-07-013143-0 Simultaneous min & max using only 3*N/2 comparisons Written by Dann Corbit 9/25/2007 Donated to the public domain */ #ifdef e_type_LONG_DOUBLE typedef long double e_type; #elif defined(e_type_DOUBLE) typedef double e_type; #elif defined(e_type_FLOAT) typedef float e_type; #elif defined(e_type_UNSIGNED_LONG_LONG) typedef unsigned long long e_type; #elif defined(e_type_LONG_LONG) typedef long long e_type; #elif defined(e_type_UNSIGNED_LONG) typedef unsigned long e_type; #elif defined(e_type_LONG) typedef long e_type; #elif defined(e_type_UNSIGNED) typedef unsigned e_type; #elif defined(e_type_INT) typedef int e_type; #elif defined(e_type_SHORT) typedef short e_type; #elif defined(e_type_UNSIGNED_SHORT) typedef unsigned e_type; #elif defined(e_type_CHAR) typedef char e_type; #elif defined(e_type_UNSIGNED_CHAR) typedef unsigned char e_type; #elif defined (__cplusplus) template < class e_type // works with stl string class etc... #endif void minmax( e_type * a, // input array size_t arr_size, // array length e_type * min_e, // smallest thing found e_type * max_e // biggest thing found ) { e_type min_et; e_type max_et; size_t i, n; if (arr_size % 2) { min_et = a; max_et = a; n = 1; } else { if (a a) { max_et = a; min_et = a; } else { min_et = a; max_et = a; } n = 2; } for (i = n; i < arr_size; i += 2) { if (a[i] a[i + 1]) { max_et = max_et a[i] ? max_et : a[i]; min_et = min_et < a[i + 1] ? min_et : a[i + 1]; } else { max_et = max_et a[i + 1] ? max_et : a[i + 1]; min_et = min_et < a[i] ? min_et : a[i]; } } *min_e = min_et; *max_e = max_et; } #if defined( UNIT_TEST ) && (defined (e_type_DOUBLE) || defined( __cplusplus)) #include char string; double foo; int main(void) { size_t i = 0; double dmin, dmax; while (fgets(string, sizeof string, stdin)) { foo[i++] = atof(string); if (i 32766) break; } minmax(foo, i, &dmin, &dmax); printf("min=%f, max=%f\n", dmin, dmax); return 0;} #endif /* C:\tmp>cl /W4 /Ox /DUNIT_TEST /De_type_DOUBLE minmax.c Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. minmax.c Microsoft (R) Incremental Linker Version 8.00.50727.762 Copyright (C) Microsoft Corporation. All rights reserved. /out:minmax.exe minmax.obj C:\tmp>dir n*.txt Volume in drive C has no label. Volume Serial Number is 0890-87CA Directory of C:\tmp 04/08/2008 04:13 PM 47,206,979 n.txt 1 File(s) 47,206,979 bytes 0 Dir(s) 4,932,272,128 bytes free C:\tmp>minmax < n.txt min=0.000043, max=20920.000000 */ Jun 27 '08 #7

 P: n/a On Apr 24, 7:21*pm, flydream

 P: n/a user923005 wrote: ) On Apr 24, 7:21*pm, flydream

 P: n/a On 24 Apr, 21:28, Eugeny Myunster arr[i]) min=i; } In addition to the comments of others try counting down as it can translate to more efficient machine code. If the array has at least one item initialise max and min to the first item such as the following to replace your code above. max = min = arr; for (i = 12; --i;;) { if (arr[i] max) max = arr[i]; if (arr[i] < min) min = arr[i]; } -- Jun 27 '08 #10

 P: n/a On 25 Apr, 07:47, Willem

 P: n/a James Harris I know, only simple one: ... > for(i=0;i<12;i++) { if(arr[max]arr[i]) min=i; } In addition to the comments of others try counting down as it can translate to more efficient machine code. If the array has at least one item initialise max and min to the first item such as the following to replace your code above. max = min = arr; for (i = 12; --i;;) { if (arr[i] max) max = arr[i]; if (arr[i] < min) min = arr[i]; } It is common, when the first element is used like this, to make the loop: if (arr[i] max) max = arr[i]; else if (arr[i] < min) min = arr[i]; since no element that is max can also be < min. -- Ben. Jun 27 '08 #12

 P: n/a On 26 Apr, 00:44, Ben Bacarisse

 P: n/a "Ben Bacarisse" On 24 Apr, 21:28, Eugeny Myunster >I know, only simple one: ... >> for(i=0;i<12;i++) { if(arr[max]arr[i]) min=i; } In addition to the comments of others try counting down as it cantranslate to more efficient machine code. If the array has at leastone item initialise max and min to the first item such as thefollowing to replace your code above.max = min = arr;for (i = 12; --i;;) { if (arr[i] max) max = arr[i]; if (arr[i] < min) min = arr[i];} It is common, when the first element is used like this, to make the loop: if (arr[i] max) max = arr[i]; else if (arr[i] < min) min = arr[i]; since no element that is max can also be < min. There is a cheesy thing which can be done if branch misprediction is expensive. int Max={0}, Min = {0}; for (i = 0; i < arr_size; i++) { Max[(arr[i] Max)] = arr[i]; Min[(arr[i] < Max)] = arr[i]; } Max and Min contain "who cares what" and Max and Min contain maximum and minimum. So much for writing code that is as clear as possible and communicates the algorithm best. ** Posted from http://www.teranews.com ** Jun 27 '08 #15

 P: n/a "Eugeny Myunster" I know, only simple one: #include int main() { int min=0,max=0,i,arr; for(i=0;i<12;i++) arr[i]=rand()%31-10; for(i=0;i<12;i++) printf("%d\t",arr[i]); printf("\n"); for(i=0;i<12;i++) { if(arr[max]arr[i]) min=i; } printf("\nmax is: %d\n",arr[max]); printf("\nmin is: %d\n",arr[min]); return 0; } #include /* "Introduction to Algorithms" Cormen, Leiserson, Rivest pp. 186,187 ISBN: 0-07-013143-0 Simultaneous min & max using only 3*N/2 comparisons Written by Dann Corbit 9/25/2007 Donated to the public domain */ #ifdef e_type_LONG_DOUBLE typedef long double e_type; #elif defined(e_type_DOUBLE) typedef double e_type; #elif defined(e_type_FLOAT) typedef float e_type; #elif defined(e_type_UNSIGNED_LONG_LONG) typedef unsigned long long e_type; #elif defined(e_type_LONG_LONG) typedef long long e_type; #elif defined(e_type_UNSIGNED_LONG) typedef unsigned long e_type; #elif defined(e_type_LONG) typedef long e_type; #elif defined(e_type_UNSIGNED) typedef unsigned e_type; #elif defined(e_type_INT) typedef int e_type; #elif defined(e_type_SHORT) typedef short e_type; #elif defined(e_type_UNSIGNED_SHORT) typedef unsigned e_type; #elif defined(e_type_CHAR) typedef char e_type; #elif defined(e_type_UNSIGNED_CHAR) typedef unsigned char e_type; #elif defined (__cplusplus) template < class e_type // works with stl string class etc... #endif void minmax( e_type * a, // input array size_t arr_size, // array length e_type * min_e, // smallest thing found e_type * max_e // biggest thing found ) { e_type min_et; e_type max_et; size_t i, n; if (arr_size % 2) { min_et = a; max_et = a; n = 1; } else { if (a a) { max_et = a; min_et = a; } else { min_et = a; max_et = a; } n = 2; } for (i = n; i < arr_size; i += 2) { if (a[i] a[i + 1]) { max_et = max_et a[i] ? max_et : a[i]; min_et = min_et < a[i + 1] ? min_et : a[i + 1]; } else { max_et = max_et a[i + 1] ? max_et : a[i + 1]; min_et = min_et < a[i] ? min_et : a[i]; } } *min_e = min_et; *max_e = max_et; } #if defined( UNIT_TEST ) && (defined (e_type_DOUBLE) || defined( __cplusplus)) #include char string; double foo; int main(void) { size_t i = 0; double dmin, dmax; while (fgets(string, sizeof string, stdin)) { foo[i++] = atof(string); if (i 32766) break; } minmax(foo, i, &dmin, &dmax); printf("min=%f, max=%f\n", dmin, dmax); return 0; } #endif /* C:\tmp>cl /W4 /Ox /DUNIT_TEST /De_type_DOUBLE minmax.c Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. minmax.c Microsoft (R) Incremental Linker Version 8.00.50727.762 Copyright (C) Microsoft Corporation. All rights reserved. /out:minmax.exe minmax.obj C:\tmp>dir n*.txt Volume in drive C has no label. Volume Serial Number is 0890-87CA Directory of C:\tmp 04/08/2008 04:13 PM 47,206,979 n.txt 1 File(s) 47,206,979 bytes 0 Dir(s) 4,932,272,128 bytes free C:\tmp>minmax < n.txt min=0.000043, max=20920.000000 */ ** Posted from http://www.teranews.com ** Jun 27 '08 #16

 P: n/a On Fri, 25 Apr 2008 18:19:51 -0700, Dann Corbit wrote: There is a cheesy thing which can be done if branch misprediction is expensive. int Max={0}, Min = {0}; for (i = 0; i < arr_size; i++) { Max[(arr[i] Max)] = arr[i]; Min[(arr[i] < Max)] = arr[i]; I think you meant to write Min[(arr[i] < Min)] = arr[i]; } Max and Min contain "who cares what" and Max and Min contain maximum and minimum. Jun 27 '08 #17

 P: n/a "Dann Corbit" if (arr[i] max) max = arr[i]; else if (arr[i] < min) min = arr[i]; There is a cheesy thing which can be done if branch misprediction is expensive. Of course there will be data sets for which the branch prediction will always be correct (unless it is a very unusual system). int Max={0}, Min = {0}; for (i = 0; i < arr_size; i++) { Max[(arr[i] Max)] = arr[i]; Min[(arr[i] < Max)] = arr[i]; } Cheesy indeed! So much for writing code that is as clear as possible and communicates the algorithm best. It seems strange to me that, with computer far faster than I ever imagined, we should still be contemplating altering source code to squeeze performance from programs. I suppose it will never stop, since so many people want code that is as fast as possible, rather than fast enough. -- Ben. Jun 27 '08 #18

 P: n/a On 26 Apr, 18:28, Ben Bacarisse

 P: n/a On Apr 26, 3:22*pm, James Harris wrote: On 26 Apr, 18:28, Ben Bacarisse

### This discussion thread is closed

Replies have been disabled for this discussion. 