Median function in the C Math Library?

Question

Is there a math function in C library to calculate MEDIAN from 'n' numbers?

Answer 1

Here you go .

Answer 2

Normal 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, there are two functions for calculating the median fastest path without sorting the candidate array. Lower at least 600% faster than conventional median calculation methods. Unfortunately, they are not part of the C or STL standard library.

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 template functions , and if numbers increase or decrease (in 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 the usual types [stdint.h] (for example, uint16_t; uint32_t, etc.)

Answer 3

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

However, you can implement one (or be sure to find the code online). An effective O (n) algorithm for finding the median is called a “selection algorithm” and is associated with quick sorting. Read all about it here .

Answer 4

To calculate the median using the standard C library, use the qsort() standard library function, 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 need to write your own compare function, which will depend on the type of array element. For more information, see the manual page for qsort or view it in the Kernighan and Ritchie indexes.

Answer 5

No, there is no median in the C standard library.

Answer 6

What about std::nth_element ? If I understand the nature of the median correctly, this will give you one for an odd number of elements.

Answer 7

to get the median, you can sort the array of numbers and take:

1) if the number of elements is odd - the number in the middle

2) in the case when the number of elements is equal - the average of two numbers in the middle