Exercices sur les algorithmes de tris

6ème et dernier TD, sur les algorithmes de tris.

TD6 au Lycée Lakanal (sujet rédigé par Arnaud Basson), sur des algorithmes de tris, et des problèmes algorithmiques qui peuvent se résoudre via un (ou plusieurs) tris.

• Date : jeudi 31 mars 2016,
• Auteur : Lilian Besson, pour le cours d’informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
• Licence : MIT Licence (http://lbesson.mit-license.org).

exos_tri.echanger(t, i, j)

Fonction naïve pour échanger les valeurs des deux cases t[i] et t[j] du tableau t.

exos_tri.parcoursBulles(t)

“Parcours bulles” proposé par l’énoncé.

• Version modifiée comme demandée par la question 2., qui renvoie False si aucune modification n’a été faite, et True si au moins une modification a été faite (comme ça, le tri à bulle triABulle() fonctionne mieux en moyenne).

exos_tri.ex1_q1_a()

Ex1 Q. 1.a.

Cette fonction de parcours parcoursBulles() effectue un seul parcours du tableau t, dans l’ordre des indices croissants, et dès qu’une paire locale \((t_i, t_{i+1})\) est mal ordonnée (\(t_i > t_{i+1}\)), on l’échange pour bien l’ordonner.

exos_tri.ex1_q1_b()

Ex1 Q. 1.b.

L’élément \(x = \max(t)\) se trouve nécessairement à la fin du tableau (i.e. \(x = t[n-1]\)).

Preuve:Si ce n’est pas le cas, cela implique notamment que la dernière paire \((t_i, t_{i+1})\) est mal ordonnée, ce qui est impossible compte tenu de la dernière itération de la fonction parcoursBulles().

exos_tri.triABulle(t)

Tri sur place le tableau t en effectuant exactement n = len(t) fois le parcours décrit plus haut, parcoursBulles().

• Complexité en temps : en \(\mathcal{O}(n^2)\), dans tous les cas.
• Complexité en mémoire : en \(\mathcal{O}(1)\) (pas de mémoire additionnelle), dans tous les cas.

exos_tri.ex1_q1_c()

Ex1 Q. 1.c.

On définit l’invariant \(I(k)\) pour \(k = 0 \dots n-1\), disant qu’après k appels à parcoursBulles(), le tableau t[n-k:] est bien trié (la fin du tableau t à k éléments).

• Par définition, \(I(0)\) ne dit rien (t[n-0:] est vide), donc est vrai;
• D’après la question 1.b., le premier appel à parcoursBulles() donne \(I(1)\);
• Ensuite, on montre par récurrence immédiate que si \(I(k)\) est vrai, le k+1 ième appel à parcoursBulles() va déplacer la k+1 plus grande valeur de t à la position t[n-k-1] = t[n - (k+1)], donc t[n-(k+1):] est trié, donc \(I(k+1)\) est aussi vrai.

Ainsi, à la fin des n appels à parcoursBulles(), on a \(I(n)\) qui est vrai, c’est à dire t[0:] = t est trié. Et cela prouve la correction de l’algorithme de tri à base de parcoursBulles(), le tri à bulle, triABulle().

• Complexité en temps : en \(\mathcal{O}(n^2)\), dans tous les cas, puisque que chaque appel de parcoursBulles() est exactement en \(\mathcal{O}(n)\), et qu’on en fait exactement n.
• Complexité en mémoire : en \(\mathcal{O}(1)\) (pas de mémoire additionnelle), dans tous les cas.

exos_tri.ex1_q2()

Ex1 Q. 2.

• On peut améliorer un peu parcoursBulles() pour renvoyer True ou False selon qu’on ait fait au moins une permutation locale, ou aucune modification locale. On reste en exactement \(\mathcal{O}(n)\);
• Avec cette modification, on peut améliorer triABulle() pour s’arrêter dès qu’un des appels à parcoursBulles() a renvoyé False : le tableau est dès lors trié, inutile de continuer.
• Cette modification améliore en moyenne l’efficacité du tri, mais il reste quadratique en moyenne et dans le pire des cas.
• Pour des tableaux presque triés par contre, on gagne et on passe en \(\mathcal{O}(n)\).

exos_tri.ex2()

Ex1 Q. 1.a.

On peut penser à plusieurs algorithmes.

1. On calcule toutes les valeurs \(| t_i - t_j |\) pour \(i < j, i,j \in [0,\dots,n-1]\) (par symétrie, on peut imposer \(i < j\)). Il y en a \(m = \frac{n (n-1)}{2}\), et ensuite le calcul du minimum est linéaire en \(m\), et donc finalement ce premier algorithme est en \(\mathcal{O}(n^2)\).
2. On peut faire mieux, en observant qu’une fois le tableau \(t\) trié, qu’on \(t'\), le \(\delta'\) est le même que le \(\delta\) (en effet \(t \mapsto t'\) est juste une permutation des indices), mais qu’il se calcule facilement comme \(\min\limits_{i = 0 \dots n-2} t'_{i+1} - t'_{i}\), donc en \(\mathcal{O}(n)\). On peut trier en \(\mathcal{O}(n \log(n))\), donc finalement ce second algorithme est en \(\mathcal{O}(n \log(n))\).

• Comme toujours pour ce genre de question, il est assez difficile de prouver qu’on ne peut pas faire mieux qu’une certaine complexité.
• Ici, on a déjà obtenu \(\mathcal{O}(n \log(n))\), il faudrait prouver qu’on a aussi \(\Omega(n \log(n))\) (c’est le cas).
• Si vous êtes intéressé, je vous suggère de lire cette page Wikipédia (en anglais).

exos_tri.minDistance(t)

Implémentation naïve de la fonction décrite plus haut :

1. On trie le tableau t (en temps \(\mathcal{O}(n \log n)\));
2. On calcule les valeurs abs(ts[i] - ts[i+1]) pour i = 0 .. n - 2;
3. On calcule le minimum de ces valeurs, qu’on renvoie.

Exemples :

>>> t = [3, 2, 0, 4, 1]
>>> print(minDistance(t))
1
>>> t = [2.5, 0, 4, 1, 3]
>>> print(minDistance(t))
0.5
>>> t = [2, 3.9999, 0, 4, 1]
>>> print(round(minDistance(t), 5))
0.0001

exos_tri.estTrie(t)

Vérifie en une passe dans le tableau t qu’il est bien trié.

On rappelle la définition : t est bien trié si et seulement si :

\[\forall i,j \in [0,\dots,n-1], i < j \implies t[i] < t[j]\]

• Complexité en temps : en \(\mathcal{O}(n)\) en moyenne et dans le pire des cas, et \(\mathcal{O}(1)\) dans le meilleur cas (si les deux premières valeurs de t sont mal triées).

exos_tri.stupideTri(t)

Tri stupide qui mélange le tableau t aléatoirement tant qu’il n’est pas trié (on vérifie avec estTrie())

while not estTrie(t):
    shuffle(t)

• On utilise random.shuffle() (du module random de base de Python) pour mélanger aléatoirement le tableau t (en temps linéaire en moyenne).

exos_tri.ex3_a()

Ex3 Q.a.

Prouvons que cet algorithme stupideTri() termine presque sûrement.

Hypothèses :

• Les permutations \(\sigma\) de \(\mathfrak{S}(n)\) sont toutes équiprobables, et la fonction random.shuffle() réalise parfaitement cette hypothèse.
• Le tableau t est quelconque, constitué de n nombres flottants.

Preuve :

• Dans le pire des cas, il existe une et une seule permutation \(\sigma^*\) qui permet de trier le tableau t (et pour tout tableau, il en existe au moins une).
• À chaque parcours de la boucle while, on a donc une probabilité d’au moins \(p_n = \frac{1}{\# \mathfrak{S}(n)} = \frac{1}{n!}\) de trouver aléatoirement cette \(\sigma^*\), et donc de terminer la boucle while.
• Donc pour \(k \geq 1\), la probabilité de faire strictement plus de \(k\) parcourt de la boucle while est bornée par \({(1 - p_n)}^k\), qui tend vers \(0\) quand \(k \to +\infty\) (puisque \(0 < p_n < 1\)).
• Donc presque sûrement, la boucle while termine, puisque la probabilité qu’elle ne termine pas est \(0\) (à la limite).

exos_tri.ex3_b()

Ex3 Q.b.

Prouvons que cet algorithme stupideTri() est en \(\mathcal{O}(n \times n!)\).

Hypothèses :

• La fonction random.shuffle() fonctionne, et s’exécute en \(\mathcal{O}(n)\).
• Le tableau t est quelconque, constitué de n nombres flottants, tous distincts.

Preuve :

• Dans le pire des cas, il existe une et une seule permutation \(\sigma^*\) qui permet de trier le tableau t; pour tout tableau, il en existe au moins une; et en moyenne pour un tableau de n nombres distincts, il en existe une seule.
• À chaque parcours de la boucle while, on a donc en moyenne une probabilité d’au moins \(p_n = \frac{1}{\# \mathfrak{S}(n)} = \frac{1}{n!}\) de trouver aléatoirement cette (presque sûrement unique) \(\sigma^*\), et donc de terminer la boucle while.
• Donc en moyenne il faut \(\lceil \frac{1}{p_n} \rceil = n!\) parcours de la boucle while pour terminer.
• Chaque parcours de la boucle while effectue deux opérations : 1. d’abord vérifier que t est trié (avec estTrie(), en \(\mathcal{O}(n)\)), 2. ensuite mélanger t (avec random.shuffle(), en \(\mathcal{O}(n)\) aussi).
• Et donc, comme annoncé, il faut en moyenne \(\mathcal{O}(n!)\) parcours, chacun coutant \(\mathcal{O}(n)\), soit \(\mathcal{O}(n \times n!)\) en moyenne.

exos_tri.ex4()

Exercice 4 : Tri par insertion d’un tableau presque trié.

• Si \(k = 0\), on a rien à faire, le tableau est déjà trié, et donc le tri par insertion sera en \(\mathcal{O}(n)\).
• Maintenant, supposons \(k > 0\). Pour \(n - k\) éléments (au moins), on va devoir les déplacer, au pire en faisant \(k\) déplacements élémentaires : ça prend \(\mathcal{O}\left((n - k) \times k \right)\). Pour les \(k\) éléments (au plus), on a aucune hypothèse, mais on devra les placer au bon endroit, avec au plus \(n\) opérations élémentaires : ça prend \(\mathcal{O}\left(k \times (n - k)\right)\). Finalement ça fait \(\mathcal{O}\left(k \times (n - k) + (n - k) \times k \right) = \mathcal{O}\left(k \times (n - k) \right)\).
• Et naturellement, le cas général (i.e. aucune hypothèse sur le tableau) consiste à avoir \(k = n\), et donc on a \(\mathcal{O}\left(k \times (n - k) \right) = \mathcal{O}\left(n^2\right)\).

exos_tri.partition3regions(t, i, j)

Partition du tableau t en place à l’aide du pivot p = t[i].

• Modifie le tableau en place.
• Renvoie left et pivot, la position finale du pivot (qui satisfait i <= pivot <= j) et tel que chaque élément plus petit que t[pivot] soit à sa gauche, chaque élément plus grand que t[pivot] soit à sa droite, et chaque élément égale à t[pivot] soit au milieu, entre left et pivot.
• Toutes les opérations se font en \(\mathcal{O}(j - i + 1)\), longueur du sous-tableau t[i:j+1] manipulé.

exos_tri.ex5_b()

Ex5 Q. b.

• La fonction partition3regions() doit renvoyer deux indices, et plus un seul.
• La fonction partition() classique renvoie simplement pivot la position du pivot, ici il faut renvoyer à la fois left et right.
• left désigne le début de la région du milieu où les valeurs de t (après modification) sont égales à t[pivot], et par convention pivot est right, la position de la dernière valeur de cette région du milieu.
• Le tri rapide modifié est implémenté plus bas, cf. triRapideModifie().

exos_tri.triRapideRecModifie(t, i, j)

Sous-fonction récursive, utilise la fonction partition3regions() pour trier le sous-tableau \([t_i, \dots, t_{j-1}]\) = t[i:j] :

• On partitionne, avec la position du pivot qui vaut r,
• donc le sous-tableau [t[i]..t[r-1]] = t[i:r] ne contient que des valeurs plus petites que t[r], on le trie par un 1er appel récursif,
• et ensuite le sous-tableau [t[r+1]..t[j]] = t[r+1:j+1] ne contient que des valeurs plus grandes que t[r], on le trie par un 2ème appel récursif.

Voici le code, en faisant attention au cas de base (i == j une seule valeur, ou i > j un cas qui ne devrait jamais arriver) :

def triRapideRecModifie(t, i, j):
    if i < j:  # Si i = j, rien à faire, et i > j ne doit pas arriver
        left, right = partition(t, i, j-1)  # Attention à j-1 ici !
        triRapideRecModifie(t, i, left-1)   # On trie à le morceau de gauche, pivots exclu
        # Ici c'est left-1
        triRapideRecModifie(t, right, j)   # On trie le morceau de droite, pivots exclu
        # Attention c'est right et pas right+1

Note

Comme les fonctions précédentes, inutile de renvoyer (return) quoique ce soit, les modifications sont faites en place.

exos_tri.triRapideModifie(t)

Tri rapide pour le tableau t (de taille \(n\)), fait appel à triRapideRec().

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\mathcal{O}(n \log n)\) en moyenne (dans PRESQUE tous les cas), mais \(\mathcal{O}(n^2)\) dans le pire des cas (notamment pour un tableau déjà trié !).
• Conclusion : sous-quadratique, “en n log n”.

Exemples (avec des tableaux de 5 ou 6 éléments) :

• Avec 5 éléments, distincts :

>>> t1 = [4, 2, 3, 6, 8]
>>> t1_trie = triRapideModifie(t1)
>>> print(t1_trie)
[2, 3, 4, 6, 8]

• Avec 8 éléments, distincts :

>>> t2 = [40, 2, 3, 6, 8, 1, 0, -10]
>>> t2_trie = triRapideModifie(t2)
>>> print(t2_trie)
[-10, 0, 1, 2, 3, 6, 8, 40]

• Avec 8 éléments, presque tous égaux :

>>> t2 = [0, 1, 0, 1, 0, 1, 0, 1]
>>> t2_trie = triRapideModifie(t2)
>>> print(t2_trie)
[0, 0, 0, 0, 1, 1, 1, 1]

• Référence : Tri rapide, sur Wikipédia, sur www.sorting-algorithms.com (quick-sort).

exos_tri.ex5_c()

Ex5 Q. c. Étude de complexités.

1. Pour un tableau où tous les éléments sont égaux (déjà trié donc) :
   • le tri rapide standard sera en \(\mathcal{O}(n \log n)\) (cf. la preuve classique, le tri rapide standard ne faisant aucune hypothèse sur la répartition des nombres);
   • le tri rapide modifié standard sera par contre en \(\mathcal{O}(n)\), puisqu’un seul appel à partition3regions() permet de découvrir que la “région du milieu” constante est en fait tout le tableau, et on s’arrête juste après.
2. Pour un tableau contenant uniquement des 0 et des 1 :
   • le tri rapide standard sera en \(\mathcal{O}(n \log n)\) (cf. la preuve classique, le tri rapide standard ne faisant aucune hypothèse sur la répartition des nombres);
   • le tri rapide modifié standard sera par contre en \(\mathcal{O}(n)\), puisqu’un seul appel à partition3regions() permet de séparer les 0 des 1, et les deux morceaux sont dès lors triés (et il n’y a plus rien à faire).

exos_tri.ex6()

Exercice 6 : Inversions d’une permutation.

Exercice plus difficile, à essayer pour s’entraîner.

Pour une correction, cf. ce document ou celui là.

C’est aussi traité dans “la Bible” de l’algorithmique, « Algorithmique », par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Dunod, 3ème édition (il est au CDI de tout bon lycée de prépa).

---

Sortie du script

$ python3 exos_tri.py


Exercice 1 : Tri a bulles.


Exercice 2 : Distance minimale entre deux elements.


Exercice 3 : Tri stupide.


Exercice 4 : Tri par insertion d'un tableau presque trie.


Exercice 5 : Une modification du tri rapide.


Exercice 6 : Inversions d’une permutation.
Test automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :
Trying:
    t = [3, 2, 0, 4, 1]
Expecting nothing
ok
Trying:
    print(minDistance(t))
Expecting:
    1
ok
Trying:
    t = [2.5, 0, 4, 1, 3]
Expecting nothing
ok
Trying:
    print(minDistance(t))
Expecting:
    0.5
ok
Trying:
    t = [2, 3.9999, 0, 4, 1]
Expecting nothing
ok
Trying:
    print(round(minDistance(t), 5))
Expecting:
    0.0001
ok
Trying:
    t1 = [4, 2, 3, 6, 8]
Expecting nothing
ok
Trying:
    t1_trie = triRapideModifie(t1)
Expecting nothing
ok
Trying:
    print(t1_trie)
Expecting:
    [2, 3, 4, 6, 8]
ok
Trying:
    t2 = [40, 2, 3, 6, 8, 1, 0, -10]
Expecting nothing
ok
Trying:
    t2_trie = triRapideModifie(t2)
Expecting nothing
ok
Trying:
    print(t2_trie)
Expecting:
    [-10, 0, 1, 2, 3, 6, 8, 40]
ok
Trying:
    t2 = [0, 1, 0, 1, 0, 1, 0, 1]
Expecting nothing
ok
Trying:
    t2_trie = triRapideModifie(t2)
Expecting nothing
ok
Trying:
    print(t2_trie)
Expecting:
    [0, 0, 0, 0, 1, 1, 1, 1]
ok
19 items had no tests:
    __main__
    __main__.echanger
    __main__.estTrie
    __main__.ex1_q1_a
    __main__.ex1_q1_b
    __main__.ex1_q1_c
    __main__.ex1_q2
    __main__.ex2
    __main__.ex3_a
    __main__.ex3_b
    __main__.ex4
    __main__.ex5_b
    __main__.ex5_c
    __main__.ex6
    __main__.parcoursBulles
    __main__.partition3regions
    __main__.stupideTri
    __main__.triABulle
    __main__.triRapideRecModifie
2 items passed all tests:
   6 tests in __main__.minDistance
   9 tests in __main__.triRapideModifie
15 tests in 21 items.
15 passed and 0 failed.
Test passed.

Plus de details sur ces doctests peut etre trouve dans la documentation de Python:
https://docs.python.org/3/library/doctest.html (en anglais)

Le fichier Python se trouve ici : exos_tri.py.