Median Function in C Math Library?

Question

Is there any math function in C library to calculate MEDIAN of 'n' numbers?

Answer 1

Conventional Method: (not recommended if you are working on image processing)

/* median through qsort example */
#include <stdio.h>
#include <stdlib.h>

#define ELEMENTS 6

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, ELEMENTS, sizeof(int), compare);
  for (n=0; n<ELEMENTS; n++)
  {   printf ("%d ",values[n]); }
  printf ("median=%d ",values[ELEMENTS/2]);
  return 0;
}

However, are two functions to calculate median the fastest way without sorting the array of candidates. The following are at least 600% faster than conventional ways to calculate median. Unfortunately they are not a part of C standard Library or C++ STL.

Faster Methods:

//===================== Method 1: =============================================
//Algorithm from N. Wirth’s book Algorithms + data structures = programs of 1976    

typedef int_fast16_t elem_type ;

#ifndef ELEM_SWAP(a,b)
#define ELEM_SWAP(a,b) { register elem_type t=(a);(a)=(b);(b)=t; }

elem_type kth_smallest(elem_type a[], uint16_t n, uint16_t k)
{
    uint64_t i,j,l,m ;
    elem_type x ;
    l=0 ; m=n-1 ;
    while (l<m) {
    x=a[k] ;
    i=l ;
    j=m ;
    do {
    while (a[i]<x) i++ ;
    while (x<a[j]) j-- ;
    if (i<=j) {
    ELEM_SWAP(a[i],a[j]) ;
    i++ ; j-- ;
    }
    } while (i<=j) ;
    if (j<k) l=i ;
    if (k<i) m=j ;
    }
    return a[k] ;
}

    #define wirth_median(a,n) kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1)))

//===================== Method 2: =============================================
//This is the faster median determination method.
//Algorithm from Numerical recipes in C of 1992

elem_type quick_select_median(elem_type arr[], uint16_t n)
{
    uint16_t low, high ;
    uint16_t median;
    uint16_t middle, ll, hh;
    low = 0 ; high = n-1 ; median = (low + high) / 2;
    for (;;) {
    if (high <= low) /* One element only */
    return arr[median] ;
    if (high == low + 1) { /* Two elements only */
    if (arr[low] > arr[high])
    ELEM_SWAP(arr[low], arr[high]) ;
    return arr[median] ;
    }
    /* Find median of low, middle and high items; swap into position low */
    middle = (low + high) / 2;
    if (arr[middle] > arr[high])
    ELEM_SWAP(arr[middle], arr[high]) ;
    if (arr[low] > arr[high])
    ELEM_SWAP(arr[low], arr[high]) ;
    if (arr[middle] > arr[low])
    ELEM_SWAP(arr[middle], arr[low]) ;
    /* Swap low item (now in position middle) into position (low+1) */
    ELEM_SWAP(arr[middle], arr[low+1]) ;
    /* Nibble from each end towards middle, swapping items when stuck */
    ll = low + 1;
    hh = high;
    for (;;) {
    do ll++; while (arr[low] > arr[ll]) ;
    do hh--; while (arr[hh] > arr[low]) ;
    if (hh < ll)
    break;
    ELEM_SWAP(arr[ll], arr[hh]) ;
    }
    /* Swap middle item (in position low) back into correct position */
    ELEM_SWAP(arr[low], arr[hh]) ;
    /* Re-set active partition */
    if (hh <= median)
    low = ll;
    if (hh >= median)
    high = hh - 1;
    }
    return arr[median] ;
}
#endif

In C++ I make these templated functions and if the numbers are increasing or decreasing (one direction) for such functions use int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; types instead of regular [stdint.h] types (e.g. uint16_t; uint32_t, etc)

Answer 2

Here you go.

Answer 3

To compute the median using the standard C library, use the standard library function qsort() and then take the middle element. If the array is a and has n elements, then:

qsort(a, n, sizeof(a[0]), compare);
return a[n/2];

You have to write your own compare function which will depend on the type of an array element. For details consult the man page for qsort or look it up in the index of Kernighan and Ritchie.

Answer 4

No, there is no such function in the standard C library.

However, you can implement one (or surely find code online). An efficient O(n) algorithm for finding a median is called "selection algorithm" and is related to quicksort. Read all about it here.