Fonction médiane dans la bibliothèque mathématique C?

Question

Existe-t-il une fonction mathématique dans la bibliothèque C pour calculer le MEDIAN des nombres 'n'?

Answer 1

pour obtenir la médiane, vous pouvez trier le tableau de nombres et de prendre:

1) dans le cas où nombre d'éléments est impair - le nombre au milieu

2) dans le cas où nombre d'éléments est pair - la moyenne de deux nombres au milieu

Answer 2

Here you go.

Answer 3

Non, il n'y a pas de fonction médiane dans la bibliothèque C standard.

Answer 4

Non, cette fonction n'existe pas dans la bibliothèque C standard.

Toutefois, vous pouvez en implémenter un (ou trouver sûrement du code en ligne). Un algorithme O (n) efficace pour trouver une médiane est appelé "algorithme de sélection" et est associé à quicksort. Lisez tout à ce sujet here.

Answer 5

Pour calculer la médiane à l'aide de la bibliothèque C standard, utilisez la fonction de bibliothèque standard qsort(), puis prenez l'élément du milieu. Si le tableau est a et a n éléments, puis:

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

Vous devez écrire votre propre fonction compare qui dépendra du type d'un élément de tableau. Pour plus de détails, consultez la page man pour qsort ou recherchez-la dans l'index de Kernighan et Ritchie.

Answer 6

Méthode conventionnelle: (non recommandé si vous travaillez sur le traitement d'images)

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

Cependant, deux fonctions pour calculer la médiane la plus rapide sans tri le tableau des candidats. Ce qui suit est au moins 600% plus rapide que les méthodes conventionnelles pour calculer la médiane. Malheureusement, ils ne font pas partie de C standard Library ou C++ STL.

Des méthodes plus rapides:

//===================== 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++ je fais ces fonctions et si templated les chiffres augmentent ou diminuent (un sens) pour ces fonctions utilisent int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; types au lieu des types [stdint.h] standard (par exemple, uint16_t; uint32_t, etc)

Answer 7

Qu'en est-il de std::nth_element? Si je comprends correctement la nature de la médiane, cela vous donnerait un nombre impair d'éléments.