Une précondition

Dans cette page, on ne trie pas encore: on prépare le terrain avec des fonctions de contrôle.

Exercice

On veut écrire une fonction qui prend en argument une liste d'entiers respectant la précondition: la liste donnée en argument est triée (en ordre croissant).

On veut vérifier explicitement le respect de cette précondition avec un assert.

assert estTriee(liste), "Attention, liste doit être triée."

Votre mission est ici d'écrire la fonction estTriee permettant de contrôler le respect de la précondition:

def estTriee(liste):
    """
    liste -- liste d'entiers

    renvoie True si liste est triée en ordre croissant, False sinon.
    >>> estTriee([2, 6, 8, 9])
    True
    >>> estTriee([])
    True
    >>> estTriee([2,3,4,1])
    False
    """

Indication

Il suffit de visiter chaque élément de la liste de l'indice 0 à l'indice le plus grand en vérifiant, pour chaque élément, qu'il n'est pas plus grand que celui qui le suit.

Solution

Un code possible:

def estTriee(liste):
    """
    liste -- liste d'entiers

    renvoie True si liste est triée en ordre croissant, False sinon.
    >>> estTriee([2, 6, 8, 9])
    True
    >>> estTriee([])
    True
    >>> estTriee([2,3,4,1])
    False
    """
    for i in range(len(liste)-1):
        if liste[i] > liste[i+1]: return False
    return True

Exercice

On veut maintenant écrire une fonction qui prendra en paramètres une liste tab d'entiers et un entier k compris entre 0 et longueur(tab)-1.

Une précondition à respecter pour exécuter cette fonction sera que tab[0..k] soit triée (en ordre croissant).

tab[0..k]

La notation tab[0..k] désigne la sous-liste [tab[0], tab[1], tab[2], ..., tab[k]].

On aimerait donc maintenant écrire la fonction suivante:

def débutTrié(tab, k):
    """
    tab -- liste d'entiers
    k -- indice entre 0 et len(tab)-1.

    renvoie True si tab[0..k] est trié en ordre croissant, False sinon.
    >>> débutTrié([2, 5, 6, 3, 4], 2)
    True
    >>> débutTrié([2, 5, 6, 3, 4], 3)
    False
    """

A vous !

Solution

Un code possible:

def débutTrié(tab, k):
    """
    tab -- liste d'entiers
    k -- indice entre 0 et len(tab)-1.

    renvoie True si tab[0..k] est trié en ordre croissant, False sinon.
    >>> débutTrié([2, 5, 6, 3, 4], 2)
    True
    >>> débutTrié([2, 5, 6, 3, 4], 3)
    False
    """
    assert 0 <= k < len(tab), "Attention, k doit être un indice de tab."
    for i in range(0, k):
        if tab[i] > tab[i+1]: return False
    return True