Code source de exos_tri

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
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).
"""

from __future__ import print_function  # Python 2 compatibility

import numpy as np
import matplotlib.pyplot as plt


# %% Exercice 1 : Tri à bulles.
print("\n\nExercice 1 : Tri a bulles.")


[docs]def echanger(t, i, j): r""" Fonction naïve pour échanger les valeurs des deux cases ``t[i]`` et ``t[j]`` du tableau ``t``. """ t[i], t[j] = t[j], t[i]
[docs]def parcoursBulles(t): r""" "Parcours bulles" proposé par l'énoncé. - Version modifiée comme demandée par la `question 2. <#exos_tri.ex1_q2>`_, 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 :py:func:`triABulle` fonctionne mieux en moyenne). """ n = len(t) modif = False for i in range(n-1): if t[i] > t[i+1]: echanger(t, i, i+1) modif = True return modif
[docs]def ex1_q1_a(): r""" Ex1 Q. 1.a. Cette fonction de parcours :py:func:`parcoursBulles` effectue un seul parcours du tableau ``t``, dans l'ordre des indices croissants, et dès qu'une paire locale :math:`(t_i, t_{i+1})` est mal ordonnée (:math:`t_i > t_{i+1}`), on l'échange pour bien l'ordonner. """ pass
[docs]def ex1_q1_b(): r""" Ex1 Q. 1.b. L'élément :math:`x = \max(t)` se trouve nécessairement à la fin du tableau (i.e. :math:`x = t[n-1]`). :Preuve: Si ce n'est pas le cas, cela implique notamment que la dernière paire :math:`(t_i, t_{i+1})` est mal ordonnée, ce qui est impossible compte tenu de la dernière itération de la fonction :py:func:`parcoursBulles`. """ pass
[docs]def triABulle(t): r""" Tri sur place le tableau ``t`` en effectuant exactement ``n = len(t)`` fois le parcours décrit plus haut, :py:func:`parcoursBulles`. - Complexité en temps : en :math:`\mathcal{O}(n^2)`, dans tous les cas. - Complexité en mémoire : en :math:`\mathcal{O}(1)` (pas de mémoire additionnelle), dans tous les cas. """ n = len(t) for _ in range(n): modif = parcoursBulles(t) if not modif: break return t
[docs]def ex1_q1_c(): r""" Ex1 Q. 1.c. On définit l'invariant :math:`I(k)` pour :math:`k = 0 \dots n-1`, disant qu'après k appels à :py:func:`parcoursBulles`, le tableau ``t[n-k:]`` est bien trié (la fin du tableau ``t`` à ``k`` éléments). - Par définition, :math:`I(0)` ne dit rien (``t[n-0:]`` est vide), donc est vrai; - D'après la `question 1.b. <#exos_tri.ex1_q1_b>`_, le premier appel à :py:func:`parcoursBulles` donne :math:`I(1)`; - Ensuite, on montre par récurrence immédiate que si :math:`I(k)` est vrai, le ``k+1`` ième appel à :py:func:`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 :math:`I(k+1)` est aussi vrai. Ainsi, à la fin des ``n`` appels à :py:func:`parcoursBulles`, on a :math:`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 :py:func:`parcoursBulles`, le **tri à bulle**, :py:func:`triABulle`. - Complexité en temps : en :math:`\mathcal{O}(n^2)`, dans tous les cas, puisque que chaque appel de :py:func:`parcoursBulles` est exactement en :math:`\mathcal{O}(n)`, et qu'on en fait exactement ``n``. - Complexité en mémoire : en :math:`\mathcal{O}(1)` (pas de mémoire additionnelle), dans tous les cas. """ pass
[docs]def ex1_q2(): r""" Ex1 Q. 2. - On peut améliorer un peu :py:func:`parcoursBulles` pour renvoyer ``True`` ou ``False`` selon qu'on ait fait au moins une permutation locale, ou aucune modification locale. On reste en exactement :math:`\mathcal{O}(n)`; - Avec cette modification, on peut améliorer :py:func:`triABulle` pour s'arrêter dès qu'un des appels à :py:func:`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 :math:`\mathcal{O}(n)`. """ pass
# %% Exercice 2 : Distance minimale entre deux éléments. print("\n\nExercice 2 : Distance minimale entre deux elements.")
[docs]def ex2(): r""" Ex1 Q. 1.a. On peut penser à plusieurs algorithmes. 1. On calcule *toutes* les valeurs :math:`| t_i - t_j |` pour :math:`i < j, i,j \in [0,\dots,n-1]` (par symétrie, on peut imposer :math:`i < j`). Il y en a :math:`m = \frac{n (n-1)}{2}`, et ensuite le calcul du minimum est linéaire en :math:`m`, et donc finalement ce premier algorithme est en :math:`\mathcal{O}(n^2)`. 2. On peut faire mieux, en observant qu'une fois le tableau :math:`t` trié, qu'on :math:`t'`, le :math:`\delta'` est le même que le :math:`\delta` (en effet :math:`t \mapsto t'` est juste une permutation des indices), mais qu'il se calcule facilement comme :math:`\min\limits_{i = 0 \dots n-2} t'_{i+1} - t'_{i}`, donc en :math:`\mathcal{O}(n)`. On peut trier en :math:`\mathcal{O}(n \log(n))`, donc finalement ce second algorithme est en :math:`\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 :math:`\mathcal{O}(n \log(n))`, il faudrait prouver qu'on a aussi :math:`\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) <https://en.wikipedia.org/wiki/Element_distinctness_problem>`_. """ pass
[docs]def minDistance(t): r""" Implémentation naïve de la fonction décrite plus haut : 1. On trie le tableau ``t`` (en temps :math:`\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 """ ts = sorted(t) return min(abs(ts[i] - ts[i+1]) for i in range(len(ts) - 1))
# %% Exercice 3 : Tri stupide. print("\n\nExercice 3 : Tri stupide.") from random import shuffle
[docs]def estTrie(t): r""" 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 : .. math:: \forall i,j \in [0,\dots,n-1], i < j \implies t[i] < t[j] - Complexité en temps : en :math:`\mathcal{O}(n)` en moyenne et dans le pire des cas, et :math:`\mathcal{O}(1)` dans le meilleur cas (si les deux premières valeurs de ``t`` sont mal triées). """ n = len(t) for i in range(n-1): if t[i] > t[i+1]: return False return True
[docs]def stupideTri(t): r""" Tri stupide qui mélange le tableau ``t`` aléatoirement tant qu'il n'est pas trié (on vérifie avec :py:func:`estTrie`) :: while not estTrie(t): shuffle(t) - On utilise :py:func:`random.shuffle` (du module :py:mod:`random` de base de Python) pour mélanger aléatoirement le tableau ``t`` (en temps linéaire en moyenne). """ while not estTrie(t): shuffle(t) return t
[docs]def ex3_a(): r""" Ex3 Q.a. Prouvons que cet algorithme :py:func:`stupideTri` termine presque sûrement. **Hypothèses :** - Les permutations :math:`\sigma` de :math:`\mathfrak{S}(n)` sont toutes équiprobables, et la fonction :py:func:`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 :math:`\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 :math:`p_n = \frac{1}{\# \mathfrak{S}(n)} = \frac{1}{n!}` de trouver aléatoirement cette :math:`\sigma^*`, et donc de terminer la boucle ``while``. - Donc pour :math:`k \geq 1`, la probabilité de faire strictement plus de :math:`k` parcourt de la boucle ``while`` est bornée par :math:`{(1 - p_n)}^k`, qui tend vers :math:`0` quand :math:`k \to +\infty` (puisque :math:`0 < p_n < 1`). - Donc presque sûrement, la boucle ``while`` termine, puisque la probabilité qu'elle ne termine pas est :math:`0` (à la limite). """ pass
[docs]def ex3_b(): r""" Ex3 Q.b. Prouvons que cet algorithme :py:func:`stupideTri` est en :math:`\mathcal{O}(n \times n!)`. **Hypothèses :** - La fonction :py:func:`random.shuffle` fonctionne, et s'exécute en :math:`\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 :math:`\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 :math:`p_n = \frac{1}{\# \mathfrak{S}(n)} = \frac{1}{n!}` de trouver aléatoirement cette (presque sûrement unique) :math:`\sigma^*`, et donc de terminer la boucle ``while``. - Donc en moyenne il faut :math:`\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 :py:func:`estTrie`, en :math:`\mathcal{O}(n)`), 2. ensuite mélanger ``t`` (avec :py:func:`random.shuffle`, en :math:`\mathcal{O}(n)` aussi). - Et donc, comme annoncé, il faut en moyenne :math:`\mathcal{O}(n!)` parcours, chacun coutant :math:`\mathcal{O}(n)`, soit :math:`\mathcal{O}(n \times n!)` en moyenne. """ pass
# %% Exercice 4 : Tri par insertion d'un tableau presque trié. print("\n\nExercice 4 : Tri par insertion d'un tableau presque trie.")
[docs]def ex4(): r""" Exercice 4 : Tri par insertion d'un tableau presque trié. - Si :math:`k = 0`, on a rien à faire, le tableau est déjà trié, et donc le tri par insertion sera en :math:`\mathcal{O}(n)`. - Maintenant, supposons :math:`k > 0`. Pour :math:`n - k` éléments (au moins), on va devoir les déplacer, au pire en faisant :math:`k` déplacements élémentaires : ça prend :math:`\mathcal{O}\left((n - k) \times k \right)`. Pour les :math:`k` éléments (au plus), on a aucune hypothèse, mais on devra les placer au bon endroit, avec au plus :math:`n` opérations élémentaires : ça prend :math:`\mathcal{O}\left(k \times (n - k)\right)`. Finalement ça fait :math:`\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 :math:`k = n`, et donc on a :math:`\mathcal{O}\left(k \times (n - k) \right) = \mathcal{O}\left(n^2\right)`. """ pass
# %% Exercice 5 : Une modification du tri rapide. print("\n\nExercice 5 : Une modification du tri rapide.") # TODO
[docs]def partition3regions(t, i, j): r""" 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 :math:`\mathcal{O}(j - i + 1)`, longueur du sous-tableau ``t[i:j+1]`` manipulé. """ if i == j: # Tableau à une seule valeur return i, i # print("--> t = {} ...".format(t)) valeurPivot = t[i] # print(" i = {}, j = {}, pivot = {} ...".format(i, j, valeurPivot)) gauche = i+1 droite = j fini = False while not fini: while (gauche <= droite) and (t[gauche] < valeurPivot): gauche += 1 milieu = gauche while (milieu <= droite) and (t[milieu] == valeurPivot): milieu += 1 while (droite >= milieu) and (t[droite] > valeurPivot): droite -= 1 if droite < milieu: fini = True else: echanger(t, milieu, droite) # On a fini ! On place le pivot à la bonne position # if not(i <= gauche <= j): # print("partition3regions(t, i = {}, j = {}) : Erreur avec gauche = {} a la fin".format(i, j, gauche)) # if not(i <= milieu <= j): # print("partition3regions(t, i = {}, j = {}) : Erreur avec milieu = {} a la fin".format(i, j, milieu)) # if not(i <= droite <= j): # print("partition3regions(t, i = {}, j = {}) : Erreur avec droite = {} a la fin".format(i, j, droite)) # print(" gauche = {}, milieu = {}, droite = {} ...".format(gauche, milieu, droite)) left, right = (lambda x, y: (min(x, y), max(x, y)))(milieu, droite) # print(" left = {}, right = {} ...".format(left, right)) echanger(t, i, left) # print("<-- t = {} ...".format(t)) return left, right
[docs]def ex5_b(): r""" Ex5 Q. b. - La fonction :py:func:`partition3regions` doit renvoyer deux indices, et plus un seul. - La fonction :py:func:`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. :py:func:`triRapideModifie`. """ pass
[docs]def triRapideRecModifie(t, i, j): r""" Sous-fonction récursive, utilise la fonction :py:func:`partition3regions` pour trier le sous-tableau :math:`[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) : .. code-block:: python 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. """ # Si on cherche la performance, on peut appeler un tri non récursif sur les tableaux de petites tailles, pour gagner un peu de temps.. if i < j: # Si i = j, rien à faire, et i > j ne doit pas arriver left, right = partition3regions(t, i, j) # if not(i <= right <= j): # print("triRapideRecModifie(t, i = {}, j = {}) : erreur avec right = {}.".format(i, j, right)) # if not(i <= left <= j): # print("triRapideRecModifie(t, i = {}, j = {}) : erreur avec left = {}.".format(i, j, left)) # if not(left <= right): # print("tiRapideRecModifie(t, i = {}, j = {}) : erreur avec left = {} > right = {}.".format(i, j, left, right)) triRapideRecModifie(t, i, left-1) # On trie à le morceau de gauche, pivots exclu triRapideRecModifie(t, right, j) # On trie le morceau de droite, pivots exclu return t
[docs]def triRapideModifie(t): r""" Tri rapide pour le tableau ``t`` (de taille :math:`n`), fait appel à :py:func:`triRapideRec`. - Complexité en *espace* : :math:`\mathcal{O}(n)`. - Complexité en *temps* : :math:`\mathcal{O}(n \log n)` en moyenne (dans PRESQUE tous les cas), mais :math:`\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 <https://fr.wikipedia.org/wiki/Tri_rapide>`_, `sur www.sorting-algorithms.com (quick-sort) <http://www.sorting-algorithms.com/quick-sort>`_. """ n = len(t) if n < 2: return t else: return triRapideRecModifie(t, 0, n-1)
[docs]def ex5_c(): r""" 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 :math:`\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 :math:`\mathcal{O}(n)`, puisqu'un seul appel à :py:func:`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 :math:`\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 :math:`\mathcal{O}(n)`, puisqu'un seul appel à :py:func:`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). """ pass
# %% Exercice 6 : Inversions d’une permutation. print("\n\nExercice 6 : Inversions d’une permutation.")
[docs]def ex6(): r""" Exercice 6 : Inversions d’une permutation. Exercice plus difficile, à essayer pour s'entraîner. Pour une correction, cf. `ce document <http://lwh.free.fr/pages/algo/tri/tri_insertion.html>`_ ou `celui là <http://www-verimag.imag.fr/~wack/ALGO5/Tris_insertion_selection-corrige.pdf>`_. C'est aussi traité dans `"la Bible" de l'algorithmique <https://en.wikipedia.org/wiki/Introduction_to_Algorithms>`_, « 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). """ pass
# %% Fin de la correction. if __name__ == '__main__': from doctest import testmod print("Test automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :") testmod(verbose=True) testmod() # testmod() print("\nPlus de details sur ces doctests peut etre trouve dans la documentation de Python:\nhttps://docs.python.org/3/library/doctest.html (en anglais)") # Fin de exos_num.py