Here's a piece of working code wrote in C to calculate the median without putting all values in an array and sorting them. It reads values from a file.
#include <stdio.h>
#include <stdlib.h>
double find_min(FILE *, double, double);
double find_max(FILE *, double, double);
int main(int argc, char *argv[]) {
int CLASSES = 2; // number of parts we create when splitting the set every single pass
double GRANULE = 0.001; // minimum precision desired, should be >=1 if numbers are integers
FILE * file_p; // data file
file_p = fopen(argv[1], "r");
int i, valueIndex1, valueIndex2, N;
// i is the index used in the for loops
// valueIndex1 is the 1st token we read from each line of the data file
// valueIndex2 is the 1st token we read from each line of the data file, in a different read
// N is the number of values in the initial set, we'll check if it's even or odd
double value;
// value is the 2nd token we read from each line of the data file, it's an observation
int count[CLASSES];
// count[n] is the number of elements in the nth part we create during a single pass
double min, max, delta;
// min is the minimum (inclusive) of the elements considered in the current pass
// max is the maximum (exclusive) of the elements considered in the current pass
// delta is the difference between the minimum and maximum values of every single part created during the current pass
double lowerBounds[CLASSES], upperBounds[CLASSES];
// lowerBounds[n] is the minimum value (inclusive) that can be in the nth part created during a pass
// upperBounds[n] is the maximum value (exclusive) that can be in the nth part created during a pass
int sum, tmpsum, limit;
sum = tmpsum = 0;
// sum is the number of elements in the parts before the ones we just create each pass
// tmpsum is the number of elements in the parts before the one we are considering during the pass
// limit is the number of elements the median should be greater than
int index_median;
// index_median is the number of the class containing the median element
short beyondPrecision; // beyondPrecision is raised to 1 if we are creating classes with a range < GRANULE
double median;
// median is where we store the value of the median before returning it
// find minimum and maximum values of the whole set
fscanf(file_p, "%d %lf", &valueIndex1, &min);
max = min;
while (fscanf(file_p, "%d %lf", &valueIndex1, &value) != EOF) {
if (value < min)
min = value;
if (value > max)
max = value;
}
N = ++valueIndex1;
// The number of values is calculated as the last of indexes found + 1
// It's equivalent to the number of lines in the file
max++; // make exclusive
// check if N is even or odd
if (N % 2)
limit = N / 2 + 1;
else
limit = N / 2;
delta = (max - min) / (CLASSES);
// define the borders of the initial frequency classes
for (i = 0; i < CLASSES; ++i) {
lowerBounds[i] = min + i*delta;
upperBounds[i] = min + (i + 1) * delta;
count[i] = 0;
}
// find the class (part) the median is in
// we keep dividing in smaller classes until we meet one of the 2 exit conditions
while (1) {
fclose(file_p);
file_p = fopen(argv[1], "r");
// fill the frequency classes
// during the first pass they are the initial classes, then they will be parts of the chosen part
while (fscanf(file_p, "%d %lf", &valueIndex2, &value) != EOF) {
for (i = 0; i < CLASSES; i++) {
if (value >= lowerBounds[i] && value < upperBounds[i])
count[i]++;
}
}
// select the class containing the median. It will be the first one with (#elements + #elements of classes on its left) > N/2
for (i = 0; i < CLASSES; ++i) {
tmpsum += count[i];
if (tmpsum > limit) {
index_median = i;
break;
}
sum += count[i];
}
min = lowerBounds[index_median];
max = upperBounds[index_median];
// if the number of elements on the left is exactly N/2, then we are done (exit condition satisfied)
// in that case, the median is calculated outside this cycle as the maximum element of the class (part) numbered index_median - 1
if (sum == limit)
break;
// if the median appears many times in the set, then we need a way to figure it out before we create classes that are too small,
// so we exit after reaching a certain fixed precision
if (max - min < GRANULE) {
beyondPrecision = 1;
index_median++;
break;
}
// set the borders of the new frequency classes (for next pass)
// they are created by dividing the class containing the median
delta = (max - min) / (CLASSES);
for (i = 0; i < CLASSES; ++i) {
lowerBounds[i] = min + i*delta;
upperBounds[i] = min + (i + 1) * delta;
count[i] = 0;
}
tmpsum = sum;
}
// now we now which class the median is in and we need to extract it
// we distinguish the 2 cases of having an ever or an odd number of observations (N)
fclose(file_p);
file_p = fopen(argv[1], "r");
if (N % 2 || beyondPrecision) { // N is odd or the median value appears more than one time
median = find_max(file_p, lowerBounds[index_median - 1], upperBounds[index_median - 1]);
} else { // N is even
double a, b;
// a is the maximum value in the left part, where the 1st value necessary to calculate the median
// b is the minimum value in the right part, where the 2nd value necessary to calculate the median
a = find_max(file_p, lowerBounds[index_median - 1], upperBounds[index_median - 1]);
fclose(file_p);
file_p = fopen(argv[1], "r");
b = find_min(file_p, lowerBounds[index_median], upperBounds[index_median]);
median = (a + b) / 2;
}
fclose(file_p);
printf("Our median is %f\n", median);
return (EXIT_SUCCESS);
}
double find_min(FILE * file_p, double lowerBound, double upperBound) {
double value, min;
int valueIndex;
min = upperBound;
while (fscanf(file_p, "%d %lf", &valueIndex, &value) != EOF) {
if (value >= lowerBound && value < upperBound && value < min)
min = value;
}
return min;
}
double find_max(FILE * file_p, double lowerBound, double upperBound) {
double value, max;
int valueIndex;
max = lowerBound;
while (fscanf(file_p, "%d %lf", &valueIndex, &value) != EOF) {
if (value >= lowerBound && value < upperBound && value > max)
max = value;
}
return max;
}
And here is the code to calculate the quartile, based on the same principle.
#include <stdio.h>
#include <stdlib.h>
double find_min(FILE *, double, double);
double find_max(FILE *, double, double);
int main(int argc, char *argv[]) {
int CLASSES = 2; // number of parts we create when splitting the set every single pass
double GRANULE = 0.001; // minimum precision desired, should be >=1 if numbers are integers
double MEDIAN = 34.2275;
FILE * file_p; // data file
file_p = fopen(argv[1], "r");
int i, valueIndex1, valueIndex2, N = 0;
// i is the index used in the for loops
// valueIndex1 is the 1st token we read from each line of the data file
// valueIndex2 is the 1st token we read from each line of the data file, in a different read
// N is the number of values in the initial set, we'll check if it's even or odd
double value;
// value is the 2nd token we read from each line of the data file, it's an observation
int count[CLASSES];
// count[n] is the number of elements in the nth part we create during a single pass
double min, max, delta;
// min is the minimum (inclusive) of the elements considered in the current pass
// max is the maximum (exclusive) of the elements considered in the current pass
// delta is the difference between the minimum and maximum values of every single part created during the current pass
double lowerBounds[CLASSES], upperBounds[CLASSES];
// lowerBounds[n] is the minimum value (inclusive) that can be in the nth part created during a pass
// upperBounds[n] is the maximum value (exclusive) that can be in the nth part created during a pass
int sum, tmpsum, limit;
sum = tmpsum = 0;
// sum is the number of elements in the parts before the ones we just create each pass
// tmpsum is the number of elements in the parts before the one we are considering during the pass
// limit is the number of elements the quartile should be greater than
int index_quartile;
// index_quartile is the number of the class containing the quartile element
short beyondPrecision; // beyondPrecision is raised to 1 if we are creating classes with a range < GRANULE
double quartile;
// quartile is where we store the value of the quartile before returning it
// find minimum and maximum values of the whole set
while (N == 0) {
fscanf(file_p, "%d %lf", &valueIndex1, &value);
if (value < MEDIAN) {
min = value;
max = min;
N++; // N is now set as a counter
}
}
while (fscanf(file_p, "%d %lf", &valueIndex1, &value) != EOF) {
if (value < MEDIAN) {
if (value < min)
min = value;
if (value > max)
max = value;
N++;
}
}
max++; // make exclusive
// check if N is even or odd
if (N % 2)
limit = N / 2 + 1;
else
limit = N / 2;
delta = (max - min) / (CLASSES);
// define the borders of the initial frequency classes
for (i = 0; i < CLASSES; ++i) {
lowerBounds[i] = min + i*delta;
upperBounds[i] = min + (i + 1) * delta;
count[i] = 0;
}
// find the class (part) the quartile is in
// we keep dividing in smaller classes until we meet one of the 2 exit conditions
while (1) {
fclose(file_p);
file_p = fopen(argv[1], "r");
// fill the frequency classes
// during the first pass they are the initial classes, then they will be parts of the chosen part
while (fscanf(file_p, "%d %lf", &valueIndex2, &value) != EOF) {
if (value < MEDIAN) {
for (i = 0; i < CLASSES; i++) {
if (value >= lowerBounds[i] && value < upperBounds[i])
count[i]++;
}
}
}
// select the class containing the quartile. It will be the first one with (#elements + #elements of classes on its left) > N/2
for (i = 0; i < CLASSES; ++i) {
tmpsum += count[i];
if (tmpsum > limit) {
index_quartile = i;
break;
}
sum += count[i];
}
min = lowerBounds[index_quartile];
max = upperBounds[index_quartile];
// if the number of elements on the left is exactly N/2, then we are done (exit condition satisfied)
// in that case, the quartile is calculated outside this cycle as the maximum element of the class (part) numbered index_quartile - 1
if (sum == limit)
break;
// if the quartile appears many times in the set, then we need a way to figure it out before we create classes that are too small,
// so we exit after reaching a certain fixed precision
if (max - min < GRANULE) {
beyondPrecision = 1;
index_quartile++;
break;
}
// set the borders of the new frequency classes (for next pass)
// they are created by dividing the class containing the quartile
delta = (max - min) / (CLASSES);
for (i = 0; i < CLASSES; ++i) {
lowerBounds[i] = min + i*delta;
upperBounds[i] = min + (i + 1) * delta;
count[i] = 0;
}
tmpsum = sum;
}
// now we now which class the quartile is in and we need to extract it
// we distinguish the 2 cases of having an ever or an odd number of observations (N)
fclose(file_p);
file_p = fopen(argv[1], "r");
if (N % 2 || beyondPrecision) { // N is odd or the quartile value appears more than one time
quartile = find_max(file_p, lowerBounds[index_quartile - 1], upperBounds[index_quartile - 1]);
} else { // N is even
double a, b;
// a is the maximum value in the left part, where the 1st value necessary to calculate the quartile
// b is the minimum value in the right part, where the 2nd value necessary to calculate the quartile
a = find_max(file_p, lowerBounds[index_quartile - 1], upperBounds[index_quartile - 1]);
fclose(file_p);
file_p = fopen(argv[1], "r");
b = find_min(file_p, lowerBounds[index_quartile], upperBounds[index_quartile]);
quartile = (a + b) / 2;
}
fclose(file_p);
printf("Our quartile is %f\n", quartile);
return (EXIT_SUCCESS);
}
double find_min(FILE * file_p, double lowerBound, double upperBound) {
double value, min;
int valueIndex;
min = upperBound;
while (fscanf(file_p, "%d %lf", &valueIndex, &value) != EOF) {
if (value >= lowerBound && value < upperBound && value < min)
min = value;
}
return min;
}
double find_max(FILE * file_p, double lowerBound, double upperBound) {
double value, max;
int valueIndex;
max = lowerBound;
while (fscanf(file_p, "%d %lf", &valueIndex, &value) != EOF) {
if (value >= lowerBound && value < upperBound && value > max)
max = value;
}
return max;
}
I remember both of them working. I wrote them together with a friend less than a year ago. I forgot the logic since then (fortunately I commented it!), but now that I'm about to use it, I'd like to have it reviewed.
I'd like your opinion on this, correctness and all.
Maybe there's an elegant way to put them together?
fclose&fopenthe same file several times. Just dorewind, (Too short for an answer, hence posted as a comment.) \$\endgroup\$