Velocity Reviews > What the fastest algorithm for find max/min in an array of integers?

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

Eugeny Myunster
Guest
Posts: n/a

 04-24-2008

I know, only simple one:

#include <stdio.h>

int main()
{
int min=0,max=0,i,arr[12];
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])
max=i;
}
for(i=0;i<12;i++)
{
if(arr[min]>arr[i])
min=i;
}
printf("\nmax is: %d\n",arr[max]);
printf("\nmin is: %d\n",arr[min]);

return 0;
}

Richard Tobin
Guest
Posts: n/a

 04-24-2008
In article <fuqqel\$7qj\$(E-Mail Removed)>,
Eugeny Myunster <(E-Mail Removed)> wrote:

>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[0] 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

Keith Thompson
Guest
Posts: n/a

 04-24-2008
Don Bruder <(E-Mail Removed)> writes:
> In article <fuqqel\$7qj\$(E-Mail Removed)>,
> Eugeny Myunster <(E-Mail Removed)> wrote:
>
>> 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) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Richard Tobin
Guest
Posts: n/a

 04-24-2008
In article <(E-Mail Removed)>,
Keith Thompson <(E-Mail Removed)> wrote:

>Um, no. Sorting the array is typically O(N*log N), whereas finding
>the min and max in a linear search is O(N).

.... as is, perhaps surprisingly, finding the median.

-- Richard
--
:wq

user923005
Guest
Posts: n/a

 04-25-2008
On Apr 24, 1:28*pm, Eugeny Myunster <(E-Mail Removed)> wrote:
> I know, only simple one:
>
> #include <stdio.h>
>
> int main()
> {
> * * * * int min=0,max=0,i,arr[12];
> * * * * 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])
> * * * * * * * * * * * * max=i;
> * * * * }
> * * * * for(i=0;i<12;i++)
> * * * * {
> * * * * * * * * if(arr[min]>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 <stdlib.h>
/*
"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[0];
max_et = a[0];
n = 1;
} else {
if (a[0] > a[1]) {
max_et = a[0];
min_et = a[1];
} else {
min_et = a[0];
max_et = a[1];
}
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 <stdio.h>

char string[32767];
double foo[32767];
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

minmax.c
Microsoft (R) Incremental Linker Version 8.00.50727.762

/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

*/

flydream
Guest
Posts: n/a

 04-25-2008
It seems that this code can not improve the performance. because the
comparison was not reduced.

On Apr 25, 9:33 am, user923005 <(E-Mail Removed)> wrote:
> On Apr 24, 1:28 pm, Eugeny Myunster <(E-Mail Removed)> wrote:
>
>
>
> > I know, only simple one:

>
> > #include <stdio.h>

>
> > int main()
> > {
> > int min=0,max=0,i,arr[12];
> > 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])
> > max=i;
> > }
> > for(i=0;i<12;i++)
> > {
> > if(arr[min]>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 <stdlib.h>
> /*
> "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[0];
> max_et = a[0];
> n = 1;
> } else {
> if (a[0] > a[1]) {
> max_et = a[0];
> min_et = a[1];
> } else {
> min_et = a[0];
> max_et = a[1];
> }
> 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 <stdio.h>
>
> char string[32767];
> double foo[32767];
> 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
>
> minmax.c
> Microsoft (R) Incremental Linker Version 8.00.50727.762
>
> /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
>
> */

user923005
Guest
Posts: n/a

 04-25-2008
On Apr 24, 7:21*pm, flydream <(E-Mail Removed)> wrote:
> It seems that this code can not improve the performance. because the
> comparison was not reduced.

2*N verse 3*N/2
Not a big improvement, but an improvement.

Willem
Guest
Posts: n/a

 04-25-2008
user923005 wrote:
) On Apr 24, 7:21*pm, flydream <(E-Mail Removed)> wrote:
)> It seems that this code can not improve the performance. because the
)> comparison was not reduced.
)
) 2*N verse 3*N/2
) Not a big improvement, but an improvement.

Ah, the good old tournament algorithm.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

James Harris
Guest
Posts: n/a

 04-25-2008
On 24 Apr, 21:28, Eugeny Myunster <(E-Mail Removed)> wrote:
> I know, only simple one:

....
> for(i=0;i<12;i++)
> {
> if(arr[max]<arr[i])
> max=i;
> }
> for(i=0;i<12;i++)
> {
> if(arr[min]>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[0];
for (i = 12; --i; {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}

--

James Harris
Guest
Posts: n/a

 04-25-2008
On 25 Apr, 07:47, Willem <(E-Mail Removed)> wrote:
> user923005 wrote:
>
> ) On Apr 24, 7:21 pm, flydream <(E-Mail Removed)> wrote:
> )> It seems that this code can not improve the performance. because the
> )> comparison was not reduced.
> )
> ) 2*N verse 3*N/2
> ) Not a big improvement, but an improvement.
>
> Ah, the good old tournament algorithm.

I'm not sure that is a tournament algorithm. What it seems to do is to
pass through the array comparing adjacent elements. Call these
elements A and B. Then if we know A > B we only need to:

compare A with max
compare B with min

The inter-element compare avoids

comparing A with min and
comparing B with max

so where a basic solution would do four comparisons the algorithm only
carries out three.

This would gain little and may cost more in mechanism on hardware
where the comparisons are single- or half-cycle but it would be good
if the comparisons were expensive.

--