void minmax(int a[], int n, int *min_ptr, int *max_ptr)How about find the max/min and the 2nd max/min value? Should implement in n + logn - 2

{

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;

else

*min_ptr = min2;

if (max1 < max2)

*max_ptr = max2;

else

*max_ptr = max1;

}

}

**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:

where 'compare_and_swap' compare two items and put the smaller to left and greater one to right.for (step =1; step < n/2; step *= 2)

for (i =0; i <n; i+= 2*step)

compare_and_swap(array[i], array[i+step]);

## No comments:

## Post a Comment