Mediana Función en C Biblioteca Matemática?

Question

¿Hay alguna función matemática en la biblioteca C para calcular MEDIAN de 'n' números?

Answer 1

para obtener la mediana puede ordenar la matriz de números y tomar:

1) en caso de que el número de elementos es extraño - el número en el medio

2) en caso de que el número de elementos es par - el promedio de dos números en el medio

Answer 2

Here you go.

Answer 3

No, no hay una función mediana en la biblioteca C estándar.

Answer 4

No, no hay tal función en la biblioteca C estándar.

Sin embargo, puede implementar uno (o seguramente encontrará el código en línea). Un algoritmo O (n) eficiente para encontrar una mediana se denomina "algoritmo de selección" y se relaciona con la ordenación rápida. Lea todo al respecto here.

Answer 5

Para calcular la mediana usando la biblioteca C estándar, use la función de biblioteca estándar qsort() y luego tome el elemento medio. Si la matriz es a y tiene n elementos, entonces:

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

Usted tiene que escribir su propia función compare que dependerá del tipo de un elemento de matriz. Para más detalles, consulte la página del manual para qsort o búsquelo en el índice de Kernighan y Ritchie.

Answer 6

método convencional: (no se recomienda si usted está trabajando en el procesamiento de imágenes)

/* 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; 
} 

Sin embargo, son dos funciones para calcular la mediana de la manera más rápida sin ordenar el conjunto de candidatos. Los siguientes son al menos un 600% más rápidos que las formas convencionales de calcular la mediana. Desafortunadamente no son parte de C Standard Library o C++ STL.

métodos más rápidos:

//===================== 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 

En C++ I hacen que estos funciones con plantilla y si los números están aumentando o disminuyendo (una dirección) para este tipo de funciones de uso int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; tipos en lugar de los tipos normales [stdint.h] (por ejemplo, uint16_t; uint32_t, etc.)

Answer 7

¿Qué hay de std::nth_element? Si estoy entendiendo correctamente la naturaleza de la mediana, esto te daría una para el número impar de elementos.