Author: Dann Corbit
Date: 18:06:38 07/20/04
Go up one level in this thread
On July 20, 2004 at 18:09:47, Antonio Senatore wrote:
>
>Hi friends:
>
>I have an array of 100 elements (positive integers) and I need to know what is
>the highest value stored in the array. Does anyone know a way faster than
>
>max_value = 0;
>
>for (i=0; i &le= 99; i++) {
> if (values[i] &ge max_value) max_value = values[i];
>}
>
>I work in C
N-1 comparisions is optimal (if you start i at 1)
See "Introduction to Algorithms"
Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest
Page 186.
It is interesting that you can simultaneously calculate min and max in 3N/2
comparisons. (same page).
I have the first edition, so your page number may be different if you have the
second edition.
Here is an algorithm to find the top K elements from an N element set in linear
expected time:
/*
**
** In the following code, every reference to CLR means:
**
** "Introduction to Algorithms"
** By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
** ISBN 0-07-013143-0
*/
/*
** CLR, page 187
*/
Etype
RandomSelect(Etype A[], size_t p, size_t r, size_t i)
{
size_t q,
k;
if (p == r)
return A[p];
q = RandomPartition(A, p, r);
k = q - p + 1;
if (i <= k)
return RandomSelect(A, p, q, i);
else
return RandomSelect(A, q + 1, r, i - k);
}
size_t
RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1) * (b - a));
return c + a;
}
/*
** CLR, page 162
*/
size_t
RandomPartition(Etype A[], size_t p, size_t r)
{
size_t i = RandRange(p, r);
Etype Temp;
Temp = A[p];
A[p] = A[i];
A[i] = Temp;
return Partition(A, p, r);
}
/*
** CLR, page 154
*/
size_t
Partition(Etype A[], size_t p, size_t r)
{
Etype x,
temp;
size_t i,
j;
x = A[p];
i = p - 1;
j = r + 1;
for (;;) {
do {
j--;
}
while (!(A[j] <= x));
do {
i++;
}
while (!(A[i] >= x));
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
} else
return j;
}
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.