Anonymous user
Averages/Median: Difference between revisions
→Quickselect algorithm: Use floating point (doubles) per instructions.
(→Quickselect algorithm: Use floating point (doubles) per instructions.) |
(→Quickselect algorithm: Use floating point (doubles) per instructions.) |
||
Line 369:
===Quickselect algorithm===
Average O(n) time:
<lang c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
Line 389 ⟶ 390:
while (left < right)
{
pivot = x[k];
swap(k, right);
for (i = pos = left; i < right; i++)
{
if (x[i] < pivot)
{
swap(i, pos);
pos++;
}
}
swap(right, pos);
if (pos == k)
{
break;
}
if (pos < k)
{
left = pos + 1;
}
else
{
right = pos - 1;
}
}
return x[k];
}
int main(void)
{
int i, length;
double *x, median, median_lower;
srandom(time(0)); // seed random()
length = random() % MAX_ELEMENTS; // random number of values
x = malloc(sizeof(double) * length);
for (i = 0; i < length; i++)
{
// shifted by RAND_MAX for negative values
// divide by a random number for floating point
x[i] = (double)(random() - RAND_MAX / 2) / (random() + 1); // + 1 to not divide by 0
}
median = quick_select(length / 2, x, length); // find middle element
if (length % 2 == 0) // Even number of elements, median is average of middle two
{
// Swap largest number below the selected median
median_lower = x[0];
for (i = 1; i < length / 2; i++)
{
if (x[i] > median_lower )
{
median_lower = x[i];
}
}
median = (median + median_lower) / 2;
}
int less = 0, more = 0, eq = 0;
for (i = 0; i < length; i++) // Verification of median
{
if (x[i] < median)
{
less ++;
}
else if (x[i] > median)
{
more ++;
}
else
{
eq ++;
}
}
printf("length: %d\nmedian: %lf\n<: %d\n>: %d\n=: %d\n", length, median, less, more, eq);
return 0;
}
</lang>
| |||