Aller au contenu

Exercices

Exercice

Appliquer le tri par insertion de la page précédente à la liste:

fruits = ['poire', 'pomme', 'abricot', 'kiwi', 'orange', 'noix', 'noisette', 'cerise', 'brugnon', 'nectarine',
'prune', 'groseille', 'framboise']

et vérifier ainsi que notre fonction de tri fonctionne également sur les chaînes de caractères.

Note

En évitant les lettres accentuées et les majuscules, la comparaison python entre deux mots correspond à l'ordre alphabétique.

Solution
def rechercheIndicePivot(tab, k):
    """
    tab -- liste d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant

    renvoie le plus petit indice i ( 0 <= i <= k-1) 
    tel que tab[i] >= tab[k]
    et renvoie k si un tel indice n'existe pas.
    """
    valeur = tab[k]
    for indice in range(0, k):
        if tab[indice] >= valeur: return indice
    return k



def insertion(tab, k):
    """
    tab -- liste d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant

    Modifie tab, en sortie:
        - tab contient les mêmes éléments qu'en entrée
        - tab[0..k] est triée en ordre croissant
        - Chaque élément de tab[k+1..] est inchangé.  
    """
    valeur = tab[k]
    # on calcule l'indice où placer valeur:
    indicePivot = rechercheIndicePivot(tab, k)
    # on remonte d'un rang tous les éléments >= valeur:
    for j in range(k-1, indicePivot-1, -1):
        tab[j+1] = tab[j]
    # on place valeur à sa nouvelle position:
    tab[indicePivot] = valeur


def triInsertion(tab):
    """
    tab -- liste d'entiers

    Modifie tab en triant ses éléments en ordre croissant
    (fonction à effet de bord, ne renvoie rien)
    """
    for k in range(1, len(tab)):
        insertion(tab, k)




#### TESTS 
fruits = ['poire', 'pomme', 'abricot', 'kiwi', 'orange', 'noix', 'noisette', 'cerise', 'brugnon', 'nectarine',
'prune', 'groseille', 'framboise']
triInsertion(fruits)
print(fruits)

On obtient:

['abricot', 'brugnon', 'cerise', 'framboise', 'groseille', 'kiwi', 'nectarine', 'noisette', 'noix', 'orange', 'poire', 'pomme', 'prune']

Exercice

On dispose de séries de notes d'élèves. Par exemple:

notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]

L'élève 0 a pour notes 8, 12 et 9, l'élève 1 a pour notes 2, 18 et 15, etc...

On aimerait maintenant trier les résultats des élèves suivant l'ordre croissant des moyennes.

Reprenez nos fonctions rechercheIndicePivot, insertion et triInsertion et apporter les modifications nécessaires afin que l'on puisse facilement obtenir ce tri suivant les moyennes.

Aide

Une modification de rechercheIndicePivotsuffit, il n'y a pas besoin d'apporter de modification à insertion et à triInsertion.

Solution
def moyenne(tab):
    """
    tab -- liste de notes

    renvoie la moyenne des notes.
    >>> moyenne([8, 14, 11])
    11
    """
    s = 0
    for note in tab:
        s += note
    return s/len(tab)



def rechercheIndicePivot(tab, k):
    """
    tab -- liste de listes d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant des moyennes

    renvoie le plus petit indice i ( 0 <= i <= k-1) 
    tel que moyenne(tab[i]) >= moyenne(tab[k])
    et renvoie k si un tel indice n'existe pas.
    """
    valeur = moyenne(tab[k])
    for indice in range(0, k):
        if moyenne(tab[indice]) >= valeur: return indice
    return k



def insertion(tab, k):
    """
    tab -- liste de listes d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant des moyennes

    Modifie tab, en sortie:
        - tab contient les mêmes éléments qu'en entrée
        - tab[0..k] est triée en ordre croissant des moyennes
        - Chaque élément de tab[k+1..] est inchangé.
    """
    valeur = tab[k]
    # on calcule l'indice où placer valeur:
    indicePivot = rechercheIndicePivot(tab, k)
    # on remonte d'un rang tous les éléments >= valeur:
    for j in range(k-1, indicePivot-1, -1):
        tab[j+1] = tab[j]
    # on place valeur à sa nouvelle position:
    tab[indicePivot] = valeur


def triInsertion(tab):
    """
    tab -- liste de listes d'entiers

    Modifie tab en triant ses éléments en ordre croissant des moyennes
    (fonction à effet de bord, ne renvoie rien)
    """
    for k in range(1, len(tab)):
        insertion(tab, k)




#### TESTS 
notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
triInsertion(notes)
print(notes)

for r in notes:
    print(f"Moyenne de {r}: {moyenne(r)}.")

Exercice (facultatif)

On dispose de séries de notes d'élèves. Par exemple:

notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]

L'élève 0 a pour notes 8, 12 et 9, l'élève 1 a pour notes 2, 18 et 15, etc...

On aimerait trier les résultats des élèves suivant différents critères. Notamment on aimerait obtenir le "rang" de chaque élève à chacun des contrôles. Il nous faut donc trier les listes de notes suivant la colonne 0 (ce qui donnera les rangs au premier contrôle), puis trier les listes de notes suivant la colonne 1 (rangs au second contrôle), etc...

Note

La note d'indice 1 de l'élève d'indice 0 s'obtient par:

>>> notes[0][1]
12

Modifier les fonctions rechercheIndicePivot, insertion et triInsertion en leur ajoutant un paramètre colonne et apporter les autres modifications nécessaires afin que l'on puisse facilement obtenir ces tris suivant les colonnes.

>>> notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
>>> triInsertion(notes, 0) # tri suivant la première note
>>> notes 
[[2, 18, 15], [8, 12, 9], [10, 11, 12], [14, 13, 17]]
>>> triInsertion(notes, 1) # tri suivant la seconde note
>>> notes
[[10, 11, 12], [8, 12, 9], [14, 13, 17], [2, 18, 15]]
>>> triInsertion(notes, 2) # tri suivant la troisième note
>>> notes
[[8, 12, 9], [10, 11, 12], [2, 18, 15], [14, 13, 17]]
Solution
def rechercheIndicePivot(tab, k, colonne):
    """
    tab -- liste de listes d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant 
    suivant les éléments de colonne

    renvoie le plus petit indice i ( 0 <= i <= k-1) 
    tel que tab[i][colonne] >= tab[k][colonne]
    et renvoie k si un tel indice n'existe pas.
    """
    valeur = tab[k][colonne]
    for indice in range(0, k):
        if  tab[indice][colonne] >=  valeur: return indice
    return k


def insertion(tab, k, colonne):
    """
    tab -- liste de listes d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant
    suivant les éléments de colonne

    Modifie tab, en sortie:
        - tab contient les mêmes éléments qu'en entrée
        - tab[0..k] est triée en ordre croissant suivant les éléments de colonne
        - Chaque élément de tab[k+1..] est inchangé.
    """
    valeur = tab[k]
    # on calcule l'indice où placer valeur:
    indicePivot = rechercheIndicePivot(tab, k, colonne)
    # on remonte d'un rang tous les éléments >= valeur:
    for j in range(k-1, indicePivot-1, -1):
        tab[j+1] = tab[j]
    # on place valeur à sa nouvelle position:
    tab[indicePivot] = valeur


def triInsertion(tab, colonne):
    """
    tab -- liste de listes d'entiers

    Modifie tab en triant ses éléments en ordre croissant suivant les éléments de colonne
    (fonction à effet de bord, ne renvoie rien)
    """
    for k in range(1, len(tab)):
        insertion(tab, k, colonne)




#### TESTS 
notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
triInsertion(notes, 2)
print(notes)