Aller au contenu

Tris

Chaque exercice est fourni avec un fichier Python à compléter et un énoncé « papier » distribué à l'élève et reproduit ci-dessous.

Remarques importantes

  1. Les exercices de cette page ne sont pas classés par ordre de « difficulté », cette notion de difficulté étant subjective et dépendante de chaque élève.

  2. Les solutions proposées ne sont que des propositions !
    Il existe d'autres codes valables pour répondre à chaque problème que ceux proposés ici : il ne faut pas hésiter à les soumettre à votre enseignant pour qu'il vous donne son avis sur les idées mises en oeuvre.

Le tableau est-il trié ?☘

Programmer la fonction verifie() qui prend en paramètre un tableau non vide de valeurs numériques et qui renvoie True si ce tableau est trié dans l’ordre croissant, False sinon.

Exemples

>>> verifie([0, 5, 8, 8, 9])
True

>>> verifie([8, 12, 4])
False

>>> verifie([-1, 4])
True

>>> verifie([5])
True

>>> verifie([])
AssertionError: Tableau vide !

  1. Compléter la définition de la fonction verifie(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    def verifie(tableau):
    """
    tableau - 
    Sortie:
    >>> verifie([0, 5, 8, 8, 9])
    True
    >>> verifie([8, 12, 4])
    False
    >>> verifie([-1, 4])
    True
    >>> verifie([5])
    True
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def verifie(tableau):
    """
    tableau - list, tableau non vide de nombres
    Sortie: bool, True si les éléments de tableau sont rangés par ordre croissant,
            False sinon
    >>> verifie([0, 5, 8, 8, 9])
    True
    >>> verifie([8, 12, 4])
    False
    >>> verifie([-1, 4])
    True
    >>> verifie([5])
    True
    """
    assert tableau != [], "Tableau vide !"
    for i in range(1, len(tableau)):
        if tableau[i] < tableau[i-1]:
            return False
    return True


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    print(verifie([0, 5, 8, 8, 9]) == True)
    print(verifie([8, 12, 4]) == False)
    print(verifie([-1, 4]) == True)
    print(verifie([5]) == True)

Tri par échange☘

On considère un tableau d'entiers tab (type list) dont les éléments sont des 0 ou des 1. On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0, la seconde n'étant pas triée et la dernière ne contenant que des 1.

Zone de 0 Zone non triée Zone de 1

Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément :

  • si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant que des 0 ;
  • si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on considère alors qu’il appartient à la zone ne contenant que des 1.

Dans tous les cas, la longueur de la zone non triée diminue de 1.

La fonction tri() qui prend en paramètre un tableau contenant uniquement des 0 et des 1, doit implémenter cet algorithme en renvoyant un tableau contenant les mêmes éléments, mais triés par ordre croissant :

Exemples

>>> tri([0, 1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 0, 1, 1, 1, 1]

>>> tri([1, 1, 1, 1, 1, 0, 0, 0, 0])
[0, 0, 0, 0, 1, 1, 1, 1, 1]

  1. Compléter la définition de la fonction trie().

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    def tri(tab):
    """
    tab - 
    Sortie:
    >>> tri([0, 1, 0, 1, 0, 1, 0, 1, 0])
    [0, 0, 0, 0, 0, 1, 1, 1, 1]
    >>> tri([1, 1, 1, 1, 1, 0, 0, 0, 0])
    [0, 0, 0, 0, 1, 1, 1, 1, 1]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def tri(tab):
    """
    tab - list, tableau contenant uniquement des 0 et des 1
    Sortie: list - tableau ayant les éléments de tab triés par ordr croissant
    >>> tri([0, 1, 0, 1, 0, 1, 0, 1, 0])
    [0, 0, 0, 0, 0, 1, 1, 1, 1]
    >>> tri([1, 1, 1, 1, 1, 0, 0, 0, 0])
    [0, 0, 0, 0, 1, 1, 1, 1, 1]
    """
    # i est le premier indice de la zone non triee, j le dernier indice.
    # Au debut, la zone non triee est le tableau entier.
    i = 0
    j = len(tab)-1
    while i < j :
        if tab[i] == 0:
            i = i+1
        else :
            valeur = tab[j]
            tab[j] = tab[i]
            tab[i] = valeur
            j = j-1
    return tab


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    print(tri([0]) == [0])
    print(tri([1]) == [1])
    print(tri([0, 1]) == [0, 1])
    print(tri([0, 0, 0, 0, 1, 0, 0, 0]) == [0, 0, 0, 0, 0, 0, 0, 1])

Tri par sélection du minimum☘

La fonction tri_selection() prend en paramètre un tableau tab de nombres entiers et modifie ce tableau par effet de bord en le triant par ordre croissant selon l’algorithme suivant :

  • on recherche le plus petit élément du tableau, et on l'échange avec l'élément d'indice 0 ;
  • on recherche le second plus petit élément du tableau, et on l'échange avec l'élément d'indice 1 ;
  • on continue de cette façon jusqu'à ce que le tableau soit entièrement trié.

Exemples

>>> T = [1, 52, 6, -9, 12]
>>> tri_selection(T)
>>> T
[-9, 1, 6, 12, 52]

>>> T = [5, 4, 3, 2, 1]
>>> tri_selection(T)
>>> T
[1, 2, 3, 4, 5]

  1. Compléter la définition de la fonction tri_selection().

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    def tri_selection(tab):
    """
    tab - 
    Sortie: 
    >>> T = [1, 52, 6, -9, 12]
    >>> tri_selection(T)
    >>> T
    [-9, 1, 6, 12, 52]

    >>> T = [5, 4, 3, 2, 1]
    >>> tri_selection(T)
    >>> T
    [1, 2, 3, 4, 5]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def tri_selection(tab):
    """
    tab - list, tableau d'éléments munis d'une relation d'ordre
    Sortie: list - tableau ayant les mêmes éléments, mais rangés par ordre croissant (algo du tri sélection)
    >>> T = [1, 52, 6, -9, 12]
    >>> tri_selection(T)
    >>> T
    [-9, 1, 6, 12, 52]

    >>> T = [5, 4, 3, 2, 1]
    >>> tri_selection(T)
    >>> T
    [1, 2, 3, 4, 5]
    """
    for i in range(len(tab)):
        mini_temp = tab[i]
        i_mini_temp = i
        for j in range(i, len(tab)):
            if tab[j] < mini_temp:
                mini_temp = tab[j]
                i_mini_temp = j
        tab[i], tab[i_mini_temp] = tab[i_mini_temp], tab[i]


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    T = [1, 2, 3, 4]
    tri_selection(T)
    print(T == [1, 2, 3, 4])

    T = [5]
    tri_selection(T)
    print(T == [5])

    T = [6, 4, 2, 1, 3, 5]
    tri_selection(T)
    print(T == [1, 2, 3, 4, 5, 6])

Insérer dans un tableau trié☘

La fonction insere() prend en argument un entier a et un tableau tab d'entiers triés par ordre croissant.
Cette fonction insère la valeur a en bonne place dans le tableau et le modifie par effet de bord.

Exemples

>>> T = [1, 2, 4, 7]
>>> insere(3, T)
>>> T
[1, 2, 3, 4, 7]

>>> insere(10, T)
>>> T
[1, 2, 3, 4, 7, 10]

  1. Compléter la définition de la fonction insere().

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    def insere(a, tab):
    """
    a - 
    tab - 
    Sortie: 
            (fonction à effet de bord)
    >>> T = [1, 2, 4, 7]
    >>> insere(3, T)
    >>> T
    [1, 2, 3, 4, 7]
    >>> insere(10, T)
    >>> T
    [1, 2, 3, 4, 7, 10]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def insere(a, tab):
    """
    a - int, entier quelconque
    tab - list, tableau d'entiers triés par ordre croissant
    Sortie: None - insère a dans tab en conservant l'ordre croissant des éléments
            (fonction à effet de bord)
    >>> T = [1, 2, 4, 7]
    >>> insere(3, T)
    >>> T
    [1, 2, 3, 4, 7]
    >>> insere(10, T)
    >>> T
    [1, 2, 3, 4, 7, 10]
    """
    tab.append(a)
    i = len(tab)-1              # indice du derner élément, donc de a
    while (i > 0) and (tab[i] < tab[i-1]):
        # On échange avec le précédent tant qu'il est plus grand
        tab[i], tab[i-1] = tab[i-1], tab[i]
        i = i-1


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    T = []
    insere(3, T)
    print(T == [3])

    insere(-2, T)
    print(T == [-2, 3])

    insere(5, T)
    print(T == [-2, 3, 5])

Tri par insertion☘

La fonction tri_insertion() prend en paramètre un tableau tab de nombres entiers et renvoie un tableau trié par ordre croissant selon l’algorithme suivant :

  • On crée un tableau T contenant le premier élément de tab.
  • A l'étape j, le sous-tableau T[0..j-1] est trié et on insère tab[j] dans ce sous-tableau en déterminant le plus petit i tel que 0 <= i <= j et T[i-1] > T[j].

Exemples

>>> tri_insertion([1, 52, 6, -9, 12]) 
[-9, 1, 6, 12, 52]

>>> tri_insertion([5, 4, 3, 2, 1]) 
[1, 2, 3, 4, 5]

  1. Compléter la définition de la fonction tri_insertion().

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    def tri_insertion(tab):
    """
    tab - 
    Sortie: 
    >>> tri_insertion([1, 52, 6, -9, 12])
    [-9, 1, 6, 12, 52]
    >>> tri_insertion([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def tri_insertion(tab):
    """
    tab - list, tableau d'éléments munis d'une relation d'ordre
    Sortie: list - tableau ayant les mêmes éléments, mais rangés par ordre croissant (algo du tri insertion)
    >>> tri_insertion([1, 52, 6, -9, 12])
    [-9, 1, 6, 12, 52]
    >>> tri_insertion([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    T = []
    for elt in tab:
        T.append(elt)
        j = len(T)-1              # indice du derner élément, donc de elt
        while (j > 0) and (T[j] < T[j-1]):
            # On échange avec le précédent tant qu'il est plus grand
            T[j], T[j-1] = T[j-1], T[j]
            j = j-1
    return T


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    print(tri_insertion([1, 2, 3, 4]) == [1, 2, 3, 4])
    print(tri_insertion([5]) == [5])
    print(tri_insertion([6, 4, 2, 1, 3, 5]) == [1, 2, 3, 4, 5, 6])

Tri par sélection du maximum☘

On considère l'algorithme de tri de tableau suivant :

  • à chaque étape, on parcourt depuis le début du tableau tous les éléments non rangés ;
  • on place en dernière position le plus grand élément.

Exemple

Avec le tableau :

41 55 21 18 12 6 25

Etape 1 : on parcourt tous les éléments du tableau, on permute le plus grand élément avec le dernier. Le tableau devient :

41 25 21 18 12 6 55

Etape 2 : on parcourt tous les éléments sauf le dernier, on permute le plus grand élément trouvé avec l'avant dernier. Le tableau devient :

6 25 21 18 12 41 55

Et ainsi de suite.

La fonction tri_selection() prend en paramètre un tableau tab de nombres entiers et trie ce tableau par ordre croissant et par effet de bord selon l’algorithme précédent.

Exemples

>>> T = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(T)
>>> T
[6, 12, 18, 21, 25, 41, 55]

  1. Compléter la définition de la fonction tri_selection().

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    def tri_selection(tab):
    """
    tab - 
    Sortie: 
            (fonction à effet de bord)
    >>> T = [41, 55, 21, 18, 12, 6, 25]
    >>> tri_selection(T)
    >>> T
    [6, 12, 18, 21, 25, 41, 55]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def tri_selection(tab):
    """
    tab - list, tableau d'éléments munis d'une relation d'ordre
    Sortie: None - Tri les éléments du tableau par ordre croissant
            (fonction à effet de bord)
    >>> T = [41, 55, 21, 18, 12, 6, 25]
    >>> tri_selection(T)
    >>> T
    [6, 12, 18, 21, 25, 41, 55]
    """
    for i in range(len(tab)-1, 0, -1):
        maxi = tab[0]
        indice_du_maxi = 0
        for j in range(i+1):
            if tab[j] > maxi:
                maxi = tab[j]
                indice_du_maxi = j
        tab[i], tab[indice_du_maxi] = tab[indice_du_maxi], tab[i]


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    T = [1, 52, 6, -9, 12]
    tri_selection(T)
    print(T == [-9, 1, 6, 12, 52])

    T = [5, 4, 3, 2, 1]
    tri_selection(T)
    print(T == [1, 2, 3, 4, 5])