#!/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