[TP.05] Utilisons le tri

On dispose d’un ensemble de données pluviométriques de 2019 en Belgique. Chacune de ces données est composée d’une date et du nombre de mm d’équivalence en eau par $m^2$ . On souhaite déterminer la mesure médiane. Celle-ci correspond à la valeur centrale de l’ensemble de données, c’est-à-dire la valeur $m$ telle que le nombre de valeurs plus petites ou égales à $m$ est identique au nombre de valeurs plus grandes ou égales à $m$ . Lorsque le nombre de mesures est pair, la médiane est égale à la moyenne des deux données centrales.

Pour votre implémentation, utilisez un tri par insertion que vous aurez implémenté vous-même (voir spécification ci-dessous).

Paste this command into your terminal:

The password to connect is

Question 1: [Validation] Un exemple de médiane

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

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

Cet exemple met en évidence la différence entre la médiane et la moyenne qui vaut 406.4. On observe que la médiane est largement moins sensible aux valeurs extrêmes (2020 dans l’exemple).

Question 2: [Validation] Un autre exemple de médiane

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 données. Il faut donc faire la moyenne des deux valeurs centrales.

Question 3: Calcul d'une médiane

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

 
#A implémenter

Question 4: Complexité temporelle

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.

$\Theta(n^2)$

$O(n^2)$

$\Omega(n)$

$\Omega(n^2)$

$\Theta(n)$

$O(n)$

Author(s)	Vincent Branders, Pierre Dupont
Deadline	19/03/2025 14:00:00
Submission limit	No limitation

Information

Sign in