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;
}
}
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