Skip to content

Tris de tableaux

Énoncé

On va travailler sur des tris classiques sur des tableaux statiques. On manipule de simples tableaux d'entiers, que l'on veut trier par ordre croissant. Dans tous les exercices ci-dessous, on procédera donc :

  • toujours par échange d'éléments ;
  • sans jamais modifier la taille du tableau ;
  • sans créer de tableau intermédiaire.

Pour tester les fonctions à implanter, on peut utiliser le programme principal ci-dessous, ainsi que la fonction permettant de créer un tableau rempli de chiffres aléatoires :

 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
#!/usr/bin/env python3

"""
  Tris de tableaux
"""

from random import randint


def cree(taille):
    """
    Cree un tableau rempli de valeurs aléatoires
    """
    return [randint(1, 9) for _ in range(taille)]

def main():
    """
    Fonction principale
    """
    for taille in range(6):  # on teste sur des tableaux de taille 0 à 5 inclus
        print("-- Taille =", taille, "--")
        tab = cree(taille)
        tab_orig = tab[:]  # copie du CONTENU du tableau
        print("Tableau initial        :", tab)
        trie_nain(tab)
        print("Tri du nain            :", tab)
        tab = tab_orig[:]
        print("Tableau initial        :", tab)
        trie_min(tab)
        print("Tri par sélect. du min :", tab)
        tab = tab_orig[:]
        print("Tableau initial        :", tab)
        trie_ins(tab)
        print("Tri par insertion      :", tab)
        print()

main()

Tri du nain de jardin

On va travailler dans cet exercice sur un tri itératif appelé le tri du nain de jardin. Son principe est très simple : un nain de jardin cherche à trier des pots de fleurs par taille croissante. Il regarde le pot devant lui :

  • s'il est plus petit que le pot à sa droite, le nain avance d'un pas vers la droite (s'il n'est pas arrivé à la fin de la file de pots) ;
  • si le pot devant lui est plus grand que le pot à sa droite, le nain échange les deux pots, et recule d'un pas vers la gauche (s'il n'est pas revenu au début de la file de pots).

Implantez une fonction trie_nain(tab) qui trie le tableau par ordre croissant en utilisant l'algorithme du nain de jardin.

Quelle est la complexité temporelle au pire cas de cet algorithme ? Et dans le meilleur cas ?

Tri par sélection du minimum

On va maintenant implanter un tri par sélection (recherche) du minimum. Si on parcours le tableau à l'aide d'un indice courant idx, on garantit la propriété (invariant) suivante pour chaque pas de l'itération :

  • tous les éléments de tab entre les indices 0 et idx - 1 inclus sont déjà triés par ordre croissant ;
  • tous les élément de tab entre les indices idx et len(tab) - 1 inclus sont dans un ordre inconnu et doivent encore être traités.

À chaque pas de l'itération, on va donc chercher la valeur minimum dans le sous-tableau de tab allant de l'indice idx à l'indice len(tab) - 1 inclus puis l'échanger avec l'élément courant tab[idx]. La propriété sera donc préservée et on pourra incrémenter idx.

Implantez :

  • une fonction recherche_min(tab, debut) qui renvoie l'indice du minimum dans le tableau en partant de l'indice debut ;
  • une fonction trie_min(tab) qui trie le tableau par ordre croissant en utilisant l'algorithme du tri par sélection du minimum.

Quelle est la complexité temporelle au pire cas de cet algorithme ? Et dans le meilleur cas ?

Tri par insertion

On va enfin implanter un tri par insertion. Son principe est un peu la réciproque de celui du tri par sélection du minimum. On doit préserver la même propriété à chaque tour de la boucle, mais au lieu de chercher l'élément minimum dans la partie droite du tableau pour l'échanger avec l'élément courant, on va plutôt insérer l'élément courant à sa place dans la partie gauche (déjà triée) du tableau.

Pour insérer un élément dans la partie gauche du tableau, on doit bien sûr décaler les éléments présents d'une case vers la droite. Pour rappel, comme on travaille sur des tableaux statiques (et pas des dynamiques), on s'interdit d'utiliser les méthodes del et insert dans cet exercice.

Implantez:

  • une fonction decale_insere(tab, idx_val) qui parcours le tableau de la droite vers la gauche à partir de l'indice idx_val - 1 pour trouver la case où insérer la valeur tab[idx_val] (c'est à dire reculer dans le tableau tant que tab[idx] est strictement supérieur à la valeur à insérer), puis insère cette valeur dans la case libérée ;
  • une fonction trie_ins(tab) qui trie le tableau par ordre croissant en utilisant l'algorithme du tri par insertion.

Quelle est la complexité temporelle au pire cas de cet algorithme ? Et dans le meilleur cas ?

Correction

Cliquez ici pour révéler la correction.

Complexités :

tris.py :

 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#!/usr/bin/env python3

"""
  Tris de tableaux
"""

from random import randint

def echange(tab, idx1, idx2):
    """
    Échange les cases d'indices idx1 et idx2 d'un tableau
    """
    tmp = tab[idx1]
    tab[idx1] = tab[idx2]
    tab[idx2] = tmp

def trie_nain(tab):
    """
    Tri d'un tableau par l'algorithme du nain de jardin
    """
    idx = 0
    while idx < len(tab) - 1:
        if tab[idx] > tab[idx + 1]:
            echange(tab, idx, idx + 1)
            if idx > 0:
                idx -= 1
        else:
            idx += 1

def recherche_min(tab, debut):
    """
    Recherche le minimum d'un tableau a partir de l'indice debut
    """
    idx_min = debut
    idx = debut + 1
    while idx < len(tab):
        if tab[idx] < tab[idx_min]:
            idx_min = idx
        idx += 1
    return idx_min

def trie_min(tab):
    """
    Tri d'un tableau par selection du minimum
    """
    idx = 0
    while idx < len(tab) - 1:
        idx_min = recherche_min(tab, idx)
        echange(tab, idx, idx_min)
        idx += 1

def decale_insere(tab, idx_val):
    """
    Recherche le point d'insertion et décale les elements au passage
    """
    val = tab[idx_val]
    idx = idx_val - 1
    while (idx >= 0) and (tab[idx] > val):
        tab[idx + 1] = tab[idx]
        idx -= 1
    tab[idx + 1] = val

def trie_ins(tab):
    """
    Tri d'un tableau par insertion
    """
    idx = 1
    while idx < len(tab):
        decale_insere(tab, idx)
        idx += 1

def cree(taille):
    """
    Cree un tableau rempli de valeurs aléatoires
    """
    return [randint(1, 9) for _ in range(taille)]

def main():
    """
    Fonction principale
    """
    for taille in range(6):  # on teste sur des tableaux de taille 0 à 5 inclus
        print("-- Taille =", taille, "--")
        tab = cree(taille)
        tab_orig = tab[:]  # copie du CONTENU du tableau
        print("Tableau initial        :", tab)
        trie_nain(tab)
        print("Tri du nain            :", tab)
        tab = tab_orig[:]
        print("Tableau initial        :", tab)
        trie_min(tab)
        print("Tri par sélect. du min :", tab)
        tab = tab_orig[:]
        print("Tableau initial        :", tab)
        trie_ins(tab)
        print("Tri par insertion      :", tab)
        print()

main()