median.c File Reference

Functions for calculating median. More...

#include "tpcclibConfig.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "tpcextensions.h"
#include "tpcstatist.h"

Go to the source code of this file.

Functions
double	statMedian (double *a, const int n)
double	statKthSmallest (double *a, const int n, const int k)

Detailed Description

Functions for calculating median.

Definition in file median.c.

Function Documentation

statKthSmallest()

double statKthSmallest	(	double *	a,
		const int	n,
		const int	k )

Returns the kth smallest value in an array of given data.

Algorithm is based on the book Wirth N. Algorithms + data structures = programs. Englewood Cliffs, Prentice-Hall, 1976.

See also

statMeanSD, doubleMean, statSortDouble, doubleNaNs

Returns

Returns the kth smallest value in a[0..n-1], or NaN in case of an error.

Parameters

a	Pointer to data array of size n; data is partially sorted. NaNs are not checked but will lead to a wrong result.
n	Length of the data array
k	The K value, 0<=K<n.

Note

The K value is zero based.

Definition at line 55 of file median.c.

  {
  //printf("\n%s(a[], %u, %u)\n", __func__, n, k); fflush(stdout);
  if(a==NULL || n<1 || k<0 || k>=n) return(nan(""));
  if(n==1) return(a[0]);
 
  int l=0, m=n-1; // note that algorithm does not work with unsigned integers
  while(l<m) {
    int i=l, j=m;
    double x=a[k]; 
    do {
      while(a[i]<x) i++;
      while(x<a[j]) j--;
      if(i<=j) {double s=a[i]; a[i]=a[j]; a[j]=s; i++; j--;}
    } while(i<=j);
    if(j<k) l=i;
    if(k<i) m=j;
  }
  return(a[k]);
}

Referenced by statMedian().

statMedian()

double statMedian	(	double *	a,
		const int	n )

Returns the median in an array of given data. Algorithm is based on the book Wirth N. Algorithms + data structures = programs. Englewood Cliffs, Prentice-Hall, 1976.

See also

statMeanSD, doubleMean, statSortDouble, statKthSmallest, doubleNaNs, doubleCopyFinite, doubleRange

Returns

Returns the median in array a[0..n-1], or NaN in case of an error.

Parameters

a	Pointer to data array of size n; data is partially sorted. NaNs are not checked but will lead to a wrong result.
n	Length of data array.

Definition at line 25 of file median.c.

  {
  if(a==NULL || n<1) return(nan(""));
  if(n==1) return(a[0]);
 
  if(n%2) {
    int k=(n-1)/2; 
    return(statKthSmallest(a, n, k));
  } else {
    int k=n/2; 
    double d1=statKthSmallest(a, n, k-1);
    double d2=statKthSmallest(a, n, k);
    return(0.5*(d1+d2));
  }
}