Calculer la médiane en c#

on dirait que d'autres réponses utilisent le tri. Ce n'est pas optimal du point de vue de la performance parce qu'il faut O(n logn) fuseau. Il est possible de calculer la médiane O(n) le temps à la place. La version généralisée de ce problème est connue sous le nom de "statistiques d'ordre n", ce qui signifie Trouver un élément K dans un ensemble tel que nous avons n éléments plus petits ou égaux à K et le reste sont plus grands ou égaux K. la statistique D'ordre 0 serait un élément minimal dans l'Ensemble (Note: certains indice d'utilisation de la littérature de 1 À N au lieu de 0 à N-1). La médiane est tout simplement (Count-1)/2 - statistiques d'ordre.

ci-dessous figure le code adopté de Introduction aux Algorithmes par Cormen et al, 3e Édition.

/// <summary>
/// Partitions the given list around a pivot element such that all elements on left of pivot are <= pivot
/// and the ones at thr right are > pivot. This method can be used for sorting, N-order statistics such as
/// as median finding algorithms.
/// Pivot is selected ranodmly if random number generator is supplied else its selected as last element in the list.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 171
/// </summary>
private static int Partition<T>(this IList<T> list, int start, int end, Random rnd = null) where T : IComparable<T>
{
    if (rnd != null)
        list.Swap(end, rnd.Next(start, end+1));

    var pivot = list[end];
    var lastLow = start - 1;
    for (var i = start; i < end; i++)
    {
        if (list[i].CompareTo(pivot) <= 0)
            list.Swap(i, ++lastLow);
    }
    list.Swap(end, ++lastLow);
    return lastLow;
}

/// <summary>
/// Returns Nth smallest element from the list. Here n starts from 0 so that n=0 returns minimum, n=1 returns 2nd smallest element etc.
/// Note: specified list would be mutated in the process.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 216
/// </summary>
public static T NthOrderStatistic<T>(this IList<T> list, int n, Random rnd = null) where T : IComparable<T>
{
    return NthOrderStatistic(list, n, 0, list.Count - 1, rnd);
}
private static T NthOrderStatistic<T>(this IList<T> list, int n, int start, int end, Random rnd) where T : IComparable<T>
{
    while (true)
    {
        var pivotIndex = list.Partition(start, end, rnd);
        if (pivotIndex == n)
            return list[pivotIndex];

        if (n < pivotIndex)
            end = pivotIndex - 1;
        else
            start = pivotIndex + 1;
    }
}

public static void Swap<T>(this IList<T> list, int i, int j)
{
    if (i==j)   //This check is not required but Partition function may make many calls so its for perf reason
        return;
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

/// <summary>
/// Note: specified list would be mutated in the process.
/// </summary>
public static T Median<T>(this IList<T> list) where T : IComparable<T>
{
    return list.NthOrderStatistic((list.Count - 1)/2);
}

public static double Median<T>(this IEnumerable<T> sequence, Func<T, double> getValue)
{
    var list = sequence.Select(getValue).ToList();
    var mid = (list.Count - 1) / 2;
    return list.NthOrderStatistic(mid);
}

Quelques remarques:

1. ce code remplace le code récursif tail de la version originale dans book in à la boucle itérative.
2. il élimine également la vérification supplémentaire inutile de la version originale lorsque start==end.
3. j'ai fourni deux versions de Median, un qui accepte IEnumerable et crée ensuite une liste. Si vous utilisez la version qui accepte IList alors garder à l'esprit qu'il modifie l'ordre dans la liste.
4. les méthodes ci-dessus calculent la médiane ou toute statistique d'ordre i dans O(n) attendu. Si vous voulez O(n) au pire moment il y a ensuite une technique pour utiliser la médiane de la médiane. Alors que cela améliorerait la performance cas pire, il dégrade cas moyen parce que constant dans O(n) est maintenant plus grand. Cependant, si vous calculez la médiane principalement sur de très grandes données, alors sa valeur à examiner.
5. la méthode NthOrderStatistics permet de passer le générateur de nombres aléatoires qui serait alors utilisé pour choisir le pivot aléatoire pendant la partition. Cela n'est généralement pas nécessaire à moins que vous sachiez que vos données ont certains motifs de sorte que le dernier élément ne sera pas assez aléatoire ou si d'une certaine façon votre code est exposé à l'extérieur pour une exploitation ciblée.
6. la définition de médiane est claire si vous ont un nombre impair d'éléments. C'est juste l'élément à l'index (Count-1)/2 dans un tableau trié. Mais quand vous même nombre d'élément (Count-1)/2 n'est plus un entier et vous avez deux médianes: la médiane inférieure Math.Floor((Count-1)/2) et Math.Ceiling((Count-1)/2). Certains manuels utilisent la médiane inférieure comme "norme" tandis que d'autres proposent d'utiliser la moyenne de deux. Cette question devient particulièrement critique pour un ensemble de deux éléments. Au-dessus du code renvoie la médiane inférieure. Si vous avez voulu à la place moyenne de Inférieur et supérieur, vous devez appeler au-dessus du code à deux reprises. Dans ce cas, assurez-vous de mesurer les performances pour vos données pour décider si vous devez utiliser le code ci-dessus VS le tri simple.
7. .net 4.5+ vous pouvez ajouter MethodImplOptions.AggresiveInlining attribut Swap<T> méthode pour une performance légèrement améliorée.

Merci Rafe, cela prend en compte les problèmes que vos replyers ont posté.

public static double GetMedian(double[] sourceNumbers) {
        //Framework 2.0 version of this method. there is an easier way in F4        
        if (sourceNumbers == null || sourceNumbers.Length == 0)
            throw new System.Exception("Median of empty array not defined.");

        //make sure the list is sorted, but use a new array
        double[] sortedPNumbers = (double[])sourceNumbers.Clone();
        Array.Sort(sortedPNumbers);

        //get the median
        int size = sortedPNumbers.Length;
        int mid = size / 2;
        double median = (size % 2 != 0) ? (double)sortedPNumbers[mid] : ((double)sortedPNumbers[mid] + (double)sortedPNumbers[mid - 1]) / 2;
        return median;
    }

decimal Median(decimal[] xs) {
  Array.Sort(xs);
  return xs[xs.Length / 2];
}

Devrait faire l'affaire.

-- EDIT --

pour ceux qui veulent le monty complet, voici la solution complète, courte, pure (un tableau d'entrée non vide est supposé):

decimal Median(decimal[] xs) {
  var ys = xs.OrderBy(x => x).ToList();
  double mid = (ys.Count - 1) / 2.0;
  return (ys[(int)(mid)] + ys[(int)(mid + 0.5)]) / 2;
}

Math.NET est une bibliothèque opensource qui offre une méthode pour calculer le Médiane. Le paquet nuget s'appelle MathNet.Objets numériques.

l'usage est assez simple:

using MathNet.Numerics.Statistics;

IEnumerable<double> data;
double median = data.Median();

Voici une version générique de la réponse de Jason

    /// <summary>
    /// Gets the median value from an array
    /// </summary>
    /// <typeparam name="T">The array type</typeparam>
    /// <param name="sourceArray">The source array</param>
    /// <param name="cloneArray">If it doesn't matter if the source array is sorted, you can pass false to improve performance</param>
    /// <returns></returns>
    public static T GetMedian<T>(T[] sourceArray, bool cloneArray = true) where T : IComparable<T>
    {
        //Framework 2.0 version of this method. there is an easier way in F4        
        if (sourceArray == null || sourceArray.Length == 0)
            throw new ArgumentException("Median of empty array not defined.");

        //make sure the list is sorted, but use a new array
        T[] sortedArray = cloneArray ? (T[])sourceArray.Clone() : sortedArray = sourceArray;
        Array.Sort(sortedArray);

        //get the median
        int size = sortedArray.Length;
        int mid = size / 2;
        if (size % 2 != 0)
            return sortedArray[mid];

        dynamic value1 = sortedArray[mid];
        dynamic value2 = sortedArray[mid - 1];
        return (sortedArray[mid] + value2) * 0.5;
    }

Voici la mise en œuvre dangereuse la plus rapide, même algorithme avant, pris de ceci source

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static unsafe void SwapElements(int* p, int* q)
    {
        int temp = *p;
        *p = *q;
        *q = temp;
    }

    public static unsafe int Median(int[] arr, int n)
    {
        int middle, ll, hh;

        int low = 0; int high = n - 1; int median = (low + high) / 2;
        fixed (int* arrptr = arr)
        {
            for (;;)
            {
                if (high <= low)
                    return arr[median];

                if (high == low + 1)
                {
                    if (arr[low] > arr[high])
                        SwapElements(arrptr + low, arrptr + high);
                    return arr[median];
                }

                middle = (low + high) / 2;
                if (arr[middle] > arr[high])
                    SwapElements(arrptr + middle, arrptr + high);

                if (arr[low] > arr[high])
                    SwapElements(arrptr + low, arrptr + high);

                if (arr[middle] > arr[low])
                    SwapElements(arrptr + middle, arrptr + low);

                SwapElements(arrptr + middle, arrptr + low + 1);

                ll = low + 1;
                hh = high;
                for (;;)
                {
                    do ll++; while (arr[low] > arr[ll]);
                    do hh--; while (arr[hh] > arr[low]);

                    if (hh < ll)
                        break;

                    SwapElements(arrptr + ll, arrptr + hh);
                }

                SwapElements(arrptr + low, arrptr + hh);

                if (hh <= median)
                    low = ll;
                if (hh >= median)
                    high = hh - 1;
            }
        }
    }

la bibliothèque NMath de CenterSpace fournit une fonction:

double[] values = new double[arraySize];
double median = NMathFunctions.Median(values);

vous pouvez choisir d'utiliser NaNMedian (si votre tableau peut contenir des valeurs nulles), mais vous aurez besoin de convertir la matrice d'un vecteur:

double median = NMathFunctions.NaNMedian(new DoubleVector(values));

Bibliothèque NMath de CenterSpace n'est pas gratuit, mais beaucoup d'universités ont des licences

dans le futur. C'est je crois aussi simple qu'il peut obtenir.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Median
{
    class Program
    {
        static void Main(string[] args)
        {
            var mediaValue = 0.0;
            var items = new[] { 1, 2, 3, 4,5 };
            var getLengthItems = items.Length;
            Array.Sort(items);
            if (getLengthItems % 2 == 0)
            {
                var firstValue = items[(items.Length / 2) - 1];
                var secondValue = items[(items.Length / 2)];
                mediaValue = (firstValue + secondValue) / 2.0;
            }
            if (getLengthItems % 2 == 1)
            {
                mediaValue = items[(items.Length / 2)];
            }
            Console.WriteLine(mediaValue);
            Console.WriteLine("Enter to Exit!");
            Console.ReadKey();
        }
    }
}

ci-dessous le code fonctionne: mais pas de manière très efficace. : (

static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());            
        int[] medList = new int[n];

        for (int x = 0; x < n; x++)
            medList[x] = int.Parse(Console.ReadLine());

        //sort the input array:
        //Array.Sort(medList);            
        for (int x = 0; x < n; x++)
        {
            double[] newArr = new double[x + 1];
            for (int y = 0; y <= x; y++)
                newArr[y] = medList[y];

            Array.Sort(newArr);
            int curInd = x + 1;
            if (curInd % 2 == 0) //even
            {
                int mid = (x / 2) <= 0 ? 0 : (newArr.Length / 2);
                if (mid > 1) mid--;
                double median = (newArr[mid] + newArr[mid+1]) / 2;
                Console.WriteLine("{0:F1}", median);
            }
            else //odd
            {
                int mid = (x / 2) <= 0 ? 0 : (newArr.Length / 2);
                double median = newArr[mid];
                Console.WriteLine("{0:F1}", median);
            }
        }

}

Mes 5 cents (car il semble plus simple/simple et suffisant pour de courtes listes):

public static T Median<T>(this IEnumerable<T> items)
{
    var i = (int)Math.Ceiling((double)(items.Count() - 1) / 2);
    if (i >= 0)
    {
        var values = items.ToList();
        values.Sort();
        return values[i];
    }

    return default(T);
}

P. S en utilisant "higher median" comme décrit par ShitalShah.