Wednesday, April 23, 2008

Find the min, max value with recursive method

void minmax(int a[], int n, int *min_ptr, int *max_ptr)
int min1, max1, min2, max2;

if (n == 2)
if (a[0] < a[1]) {
*min_ptr = a[0];
*max_ptr = a[1];
else {
*min_ptr = a[1];
*max_ptr = a[0];
else {
minmax(a, n/2, &min1, &max1);
minmax(a + n/2, n/2, &min2, &max2);
if (min1 < min2)
*min_ptr = min1;
*min_ptr = min2;
if (max1 < max2)
*max_ptr = max2;
*max_ptr = max1;
How about find the max/min and the 2nd max/min value? Should implement in n + logn - 2
Use tournament method. We divide the data into n/2 groups, and we have one comparison in each group. That costs us n/2 comparisons so far. Clearly we keep halving the number of comparisons, and use n-1 searches to establish the "winner".

To find the second place, we need only look at all the data items "beaten" by the ultimate winner. There are logn "rounds", and so logn items in that group. This means we need another logn-1 comparisons to establish second place. The implementation looks like:

for (step =1; step < n/2; step *= 2)
for (i =0; i <n; i+= 2*step)
compare_and_swap(array[i], array[i+step]);

where 'compare_and_swap' compare two items and put the smaller to left and greater one to right.

No comments:

Post a Comment