Supposons le relevé de mesures suivant, identifiez la médiane correspondante.

mesures = [2, 0, 1, 9, 2020]

Cet exemple met en évidence la différence entre la médiane et la moyenne qui vaut 406.4. On observe que la médiane est largement moins sensible aux valeurs extrêmes (2020 dans l’exemple).

Supposons le relevé de mesures suivant, identifiez la médiane correspondante.

mesures = [6, 2, 7, 4, 5, 6]

Cet exemple comporte un nombre pair de données. Il faut donc faire la moyenne des deux valeurs centrales.

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier median.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

Note: Vous pouvez, dans le corps de la fonction, faire appel aux fonctions et modules importés dans le template fourni.

def median(values):
    """
    pre: `values` est un tableau (list) d objets comparables, len(values) >= 1
    post: renvoie la mesure médiane du tableau `values` sans changer l'ordre du tableau
    """
    def insertion_sort(values):
        """
        pre: `values` est un tableau (list) d objets comparables
        post: renvoie un tableau trié par ordre croissant, le tableau `values` passé en paramètre ne peut pas être modifié.
        """
        pass
    pass

#A implémenter

Quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.