#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
r""" TP7 au Lycée Lakanal (sujet rédigé par Arnaud Basson), sur les algorithmes de tris.
- *Date :* 18 février et 10 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).
-----------------------------------------------------------------------------
Quelques sites utiles :
- `Implémentations d'algorithmes de tris <https://fr.wikibooks.org/wiki/Impl%C3%A9mentation_d'algorithmes_classiques/Algorithmes_de_tri>`_, sur `WikiBooks <https://fr.wikibooks.org/>`_,
- Un petit site permettant la visualisation des différents tris : `<http://www.sorting-algorithms.com/>`_,
- `Algorithmes de tris, sur Wikipédia <https://fr.wikipedia.org/wiki/Algorithme_de_tri>`_,
- `Comparaison d'algorithmes de tris <https://fr.wikipedia.org/wikiAlgorithme_de_tri#Comparaison_des_algorithmes>`_, aussi sur Wikipédia.
**Convention :** on dira qu'un tableau ``t`` est *trié* lorsqu'il est trié en ordre croissant, c'est à dire :
.. math:: \forall i, j \in \{1,\dots,n\}, i < j \implies \texttt{t[i]} = t_i \leq t_j = \texttt{t[j]}
**Autre convention :** la plupart des fonctions de tris décrites ci-dessus modifient le tableau ``t`` **en place**, c'est à dire qu'elles écrivent dans ``t`` (et n'ont donc rien à renvoyer).
"""
from __future__ import print_function, division # Python 2 compatibility
import numpy as np
# import matplotlib.pyplot as plt
import time
import random
# %% Exercice I.1
if __name__ == '__main__':
print("\n\nI.1. Tri par insertion.")
[docs]def triInsertion(t):
r""" Tri par insertion pour le tableau ``t`` (de taille :math:`n`).
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n^2)` dans le pire des cas, :math:`\mathcal{O}(n)` dans les meilleurs cas (déjà trié, ou presque trié), et :math:`\mathcal{O}(n^2)` en moyenne.
- Conclusion : **quadratique**.
Exemples (avec des tableaux de 5 ou 6 éléments) :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]
>>> t1_trie = triInsertion(t1)
>>> print(t1_trie)
[2, 3, 4, 6, 8]
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]
>>> t2_trie = triInsertion(t2)
>>> print(t2_trie)
[-1, 2, 3, 4, 6, 8]
- Référence : `Tri par insertion, sur Wikipédia <https://fr.wikipedia.org/wiki/Tri_par_insertion>`_, `sur www.sorting-algorithms.com (insertion-sort) <http://www.sorting-algorithms.com/insertion-sort>`_.
- Note : le tri par insertion est un tri par comparaison, mais il n'effectue pas d'échange (avec :py:func:`echanger`).
- Cet algorithme de tri, et presque tous les suivants, sont **en place** : ils modifient le tableau donné en entrée.
"""
# t_trie = t[::] # Copie de t
t_trie = t # On modifie directement t.
for j in range(1, len(t_trie)):
i = j - 1
# On cherche a déplacer t[j] exactement au bon endroit
t_j = t_trie[j]
while i > -1 and t_trie[i] > t_j:
# Tant qu'on doit le déplacer
t_trie[i + 1] = t_trie[i]
i -= 1
# Il est au bon endroit !
t_trie[i + 1] = t_j
# On a fini !
return t_trie
# return sorted(t) # Done
# %% Exercice I.2
if __name__ == '__main__':
print("\n\nI.2. Tri rapide.")
[docs]def echanger(t, i, j):
r""" Fonction classique, pour échanger ``t[i]`` et ``t[j]`` en place, c'est très simple en Python
.. code-block:: python
def echanger(t, i, j):
t[i], t[j] = t[j], t[i]
Dans d'autres langages, on a besoin d'une valeur intermédiaire (``tmp``) :
.. code-block:: python
def echanger_avec_tmp(t, i, j):
tmp = t[j]
t[j] = t[i]
t[i] = tmp
"""
t[i], t[j] = t[j], t[i]
[docs]def partition(t, i, j):
r""" Partition du tableau ``t`` **en place** à l'aide du pivot ``t[i]``.
- Modifie le tableau **en place**.
- Renvoie la position finale du pivot, ``pivot`` (qui satisfait ``i <= pivot <= j``) et tel que chaque élément plus petit que ``t[pivot]`` soit à sa gauche et chaque élément plus grand que ``t[pivot]`` soit à sa droite.
- Toutes les opérations se font en :math:`\mathcal{O}(j - i + 1)`, longueur du sous-tableau manipulé.
- Cette impémentation (`voir la source <_modules/TP7.html#partition>`_) est l'implémentation impérative *"classique"*, comme faite en cours.
.. code-block:: python
def partition(t, i, j):
valeurPivot = t[i]
gauche = i+1
droite = j
fini = False
while not fini:
while (gauche <= droite) and (t[gauche] <= valeurPivot):
gauche += 1
while (droite >= gauche) and (t[droite] > valeurPivot):
droite -= 1
if droite < gauche:
fini = True
else:
echanger(t, gauche, droite)
# On a fini ! On place le pivot a la bonne position
echanger(t, i, droite)
return droite
Exemples (avec des tableaux de 5 ou 6 éléments) :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]; print(t1[0:4])
[4, 2, 3, 6]
>>> pivot = partition(t1, 0, 4)
>>> print(t1); print(pivot) # 2, 3 < 4 ont ete deplace
[3, 2, 4, 6, 8]
2
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]; print(t2[2:6])
[3, 6, 8, -1]
>>> pivot = partition(t2, 2, 5)
>>> print(t2); print(pivot) # -1 < 3 a ete deplace
[4, 2, -1, 3, 8, 6]
3
.. note::
- Mais si on utilisait des sous-tableaux (``t[i:j]``) ou des listes en compréhensions ?
- Le temps passé à recopier des tableaux et sous-tableaux, et à construire et concaténer des listes en compréhensions sera trop important.
- Mais si vous êtes curieux, une autre implémentation est donnée plus bas : :py:func:`partitionAvecRecopies`.
"""
if i == j:
return i
valeurPivot = t[i]
gauche = i + 1
droite = j
fini = False
while not fini:
while (gauche <= droite) and (t[gauche] <= valeurPivot):
gauche += 1
while (droite >= gauche) and (t[droite] > valeurPivot):
droite -= 1
if droite < gauche:
fini = True
else:
echanger(t, gauche, droite)
# On a fini ! On place le pivot à la bonne position
assert i <= droite <= j
echanger(t, i, droite)
return droite
[docs]def partitionAvecRecopies(t, i, j):
r""" Une autre implémentation de la fonction de partition, avec des une recopie sous forme de sous-tableau, ça termine par :
.. code-block:: python
def partitionAvecRecopies(t, i, j):
pivot = i
p = t[pivot]
t_gauche = []
t_pivot = []
t_droite = []
for k in range(i, j + 1):
if t[k] < p:
t_gauche.append(t[k])
elif t[k] == p:
t_pivot.append(t[k])
else:
t_droite.append(t[k])
lg = len(t_gauche)
# On réordonne
t[i:j + 1] = t_gauche + t_pivot + t_droite
# Et l'indice du pivot correspond à l'offset i, et à la longueur du tableau de gauche
return i + lg
t[i:j + 1] = t_gauche + t_pivot + t_droite
.. attention:: N'est pas aussi efficace que :py:func:`partition`.
"""
pivot = i
p = t[pivot]
t_gauche = []
t_pivot = []
t_droite = []
for k in range(i, j + 1):
if t[k] < p:
t_gauche.append(t[k])
elif t[k] == p:
t_pivot.append(t[k])
else:
t_droite.append(t[k])
lg = len(t_gauche)
# On réordonne
t[i:j + 1] = t_gauche + t_pivot + t_droite
# Et l'indice du pivot correspond à l'offset i, et à la longueur du tableau de gauche
return i + lg
[docs]def triRapideRec(t, i, j):
r""" Sous-fonction récursive, utilise la fonction :py:func:`partition` 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 triRapideRec(t, i, j):
if i < j: # Si i = j, rien à faire, et i > j ne doit pas arriver
pivot = partition(t, i, j - 1) # Attention à j - 1 ici !
triRapideRec(t, i, pivot - 1) # On trie à gauche, pivot exclu
triRapideRec(t, pivot + 1, j) # On trie à droite, pivot exclu
.. 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
pivot = partition(t, i, j)
assert i <= pivot <= j
triRapideRec(t, i, pivot - 1) # On trie à gauche, pivot exclu
triRapideRec(t, pivot + 1, j) # On trie à droite, pivot exclu
return t
[docs]def triRapide(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 :
>>> t1 = [4, 2, 3, 6, 8]
>>> t1_trie = triRapide(t1)
>>> print(t1_trie)
[2, 3, 4, 6, 8]
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]
>>> t2_trie = triRapide(t2)
>>> print(t2_trie)
[-1, 2, 3, 4, 6, 8]
- 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 triRapideRec(t, 0, n - 1)
# return sorted(t) # Done
[docs]def tabAlea(n):
r""" Utilise :py:mod:`numpy.random` pour créer un tableau aléatoire de taille ``n``, remplis de nombres flottants uniformément tirés dans :math:`[0, 1[`.
- Comme l'énoncé le demandait, on utilise ``list(np.random.random(n))``.
- Exemple :
>>> n = 20
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> print(t) # doctest: +ELLIPSIS
[0.5488..., 0.7151..., ...]
"""
return list(np.random.random(n))
[docs]def tabAleaEntiers(n):
r""" Utilise :py:mod:`numpy.random` pour créer un tableau aléatoire de taille ``n``, remplis de nombres *entiers* uniformément tirés dans :math:`[|-2016, 2016|]`.
- Ce n'était pas demandé.
- Cette fois, on utilise ``list(np.random.randint(-2016, 2016, n))``.
- Exemple :
>>> n = 20
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAleaEntiers(n)
>>> print(t) # doctest: +ELLIPSIS
[716, 591, -363, ..., -1311]
"""
return list(np.random.randint(-2016, 2016, n))
[docs]def testTriRapide():
r""" Exemples de tris par insertion et tris rapide de tableaux à :math:`200` et :math:`1000` éléments (l'énoncé demandait d'aller jusqu'à :math:`10^6`).
Pour 200 éléments, d'abord avec des flottants, puis des entiers :
>>> n = 200
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> print(t[:3]) # doctest: +ELLIPSIS
[0.5488..., 0.7151..., ...]
>>> print(triInsertion(t1)[:3]) # doctest: +ELLIPSIS
[0.0046..., 0.0117..., ...]
>>> print(all([x == y for x, y in zip(t1, sorted(t1))])) # A-t-on trié correctement ?
True
>>> print(triRapide(t2)[:3]) # doctest: +ELLIPSIS
[0.0046..., 0.0117..., ...]
>>> print(all([x == y for x, y in zip(t2, sorted(t2))])) # A-t-on trié correctement ?
True
>>> print(all([x == y for x, y in zip(t1, t2)])) # On a bien trié pareil avec les deux algorithmes
True
Avec des entiers maintenant (on utilise :py:func:`tabAleaEntiers`) :
>>> n = 200
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAleaEntiers(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> print(t[:3]) # doctest: +ELLIPSIS
[716, 591, ...]
>>> print(triInsertion(t1)[:3]) # doctest: +ELLIPSIS
[-1932, -1930, ...]
>>> print(all([x == y for x, y in zip(t1, sorted(t1))])) # A-t-on trié correctement ?
True
>>> print(triRapide(t2)[:3]) # doctest: +ELLIPSIS
[-1932, -1930, ...]
>>> print(all([x == y for x, y in zip(t2, sorted(t2))])) # A-t-on trié correctement ?
True
On peut aussi chronométrer le temps que ça prend, en utilisant la fonction :py:func:`timeit.timeit` du `module timeit <https://docs.python.org/2/library/timeit.html>`_ (ou la commande magique `%timeit <https://ipython.readthedocs.io/en/stable/interactive/magics.html?highlight=timeit#magic-timeit>`_, dans `IPython <https://ipython.org/>`_, `qui marche très désormais très bien <https://github.com/ipython/ipython/pull/8925>`_), ou avec la fonction :py:func:`time.time` (qui donne l'heure en secondes) :
>>> import time # Module time pour avoir time.time()
>>> n = 200
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> avant = time.time()
>>> _ = triInsertion(t1) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("triInsertion: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
triInsertion: n = 200, 2.71 milli-secondes.
>>> avant = time.time()
>>> _ = triRapide(t2) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("triRapide: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
triRapide: n = 200, 0.772 milli-secondes.
Pour 1000 éléments :
>>> n = 1000
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> avant = time.time()
>>> _ = triInsertion(t1) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("triInsertion: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
triInsertion: n = 1000, 57.3 milli-secondes.
>>> avant = time.time()
>>> _ = triRapide(t2) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("triRapide: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
triRapide: n = 1000, 4.74 milli-secondes.
On observe, comme prévu, que le temps d'exécution de :py:func:`triInsertion` est environ 25 (:math:`= 5^2`) fois plus grand sur un tableau 5 fois plus grand, tandis que pour :py:func:`triRapide`, l'augmentation est plutôt de l'ordre de 6 (et :math:`\log_2(5) \cdot 5 \simeq 11.6`, pour de petits tableaux c'est cohérent).
.. note:: Pour le tri par insertion, qui est en :math:`\mathcal{O}(n^2)`, j'ai préféré garder des tableaux de tailles *plus petites* pour ne pas passer trop de temps à générer la documentation.
Mais par contre, le tri rapide est capable de trier *rapidement* des grands tableaux (comme son nom l'indique).
Premier exemple, on trie 20000 éléments en 0.12 secondes :
>>> n = 20000
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n); t0 = t[:]
>>> avant = time.time()
>>> _ = triRapide(t) # doctest: +ELLIPSIS
>>> deltaT = time.time() - avant
>>> print("triRapide: n = {}, {:.3g} secondes.".format(n, deltaT))
triRapide: n = 20000, 0.128 secondes.
>>> print(all([x == y for x, y in zip(t, sorted(t0))])) # A-t-on trié correctement ?
True
Deuxième exemple, on trie 100000 éléments en à peine 6 fois plus de temps, soit 0.731 secondes, et on est guère plus rapide que la fonction de tri de Python (:py:func:`sorted`) :
>>> n = 100000
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> avant = time.time()
>>> _ = triRapide(t1) # doctest: +ELLIPSIS
>>> deltaT = time.time() - avant
>>> print("triRapide: n = {}, {:.3g} secondes.".format(n, deltaT))
triRapide: n = 100000, 0.724 secondes.
>>> avant = time.time()
>>> _ = triRapide(t2) # doctest: +ELLIPSIS
>>> deltaT = time.time() - avant
>>> print("Python's builtin sorted: n = {}, {:.3g} secondes.".format(n, deltaT))
Python's builtin sorted: n = 100000, 0.721 secondes.
>>> print(all([x == y for x, y in zip(t1, sorted(t1))])) # A-t-on trié correctement ?
True
"""
pass
[docs]def partitionRandomise(t, i, j):
r""" Partition du tableau ``t`` **en place** à l'aide d'un pivot aléatoire, implémentation plus efficace car randomisée.
- Modifie le tableau **en place**.
- Renvoie la position finale du pivot, ``pivot`` (qui satisfait ``i <= pivot <= j``) et tel que chaque élément plus petit que ``t[pivot]`` soit à sa gauche et chaque élément plus grand que ``t[pivot]`` soit à sa droite.
- L'approche suivante a l'avantage d'être très simple à écrire et à comprendre (astuce suggéré par une élève le 18-02, merci à elle) :
.. code-block:: python
def partitionRandomise(t, i, j):
pivotRandomise = np.random.randint(i, j + 1)
echanger(t, i, pivotRandomise)
return partition(t, i, j)
- On choisit une position aléatoire pour le pivot, on le met en première place, et on appelle la fonction :py:func:`partition` (qui utilisait le pivot en première place ``t[i]``).
"""
pivotRandomise = np.random.randint(i, j + 1)
echanger(t, i, pivotRandomise)
return partition(t, i, j)
[docs]def triRapideRecRandomise(t, i, j):
r""" Sous-fonction récursive randomisée, utilise la fonction :py:func:`partitionRandomise` pour trier le sous-tableau :math:`[t_i, \dots, t_{j - 1}]`.
"""
if i < j:
pivot = partitionRandomise(t, i, j)
assert i <= pivot <= j
triRapideRecRandomise(t, i, pivot - 1)
triRapideRecRandomise(t, pivot + 1, j)
return t
[docs]def triRapideRandomise(t):
r""" Meilleure version du tri rapide, pour le tableau ``t`` (de taille :math:`n`).
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n \log n)` dans PRESQUE tous les cas.
- Conclusion : **sous-quadratique**, "en n log n".
Exemples (avec des tableaux de 5 ou 6 éléments) :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]
>>> t1_trie = triRapideRandomise(t1)
>>> print(t1_trie)
[2, 3, 4, 6, 8]
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]
>>> t2_trie = triRapideRandomise(t2)
>>> print(t2_trie)
[-1, 2, 3, 4, 6, 8]
- Référence : `Tri rapide, sur Wikipédia <https://fr.wikipedia.org/wiki/Tri_rapide>`_, `sur www.sorting-algorithms.com (quick-sort, again) <http://www.sorting-algorithms.com/quick-sort>`_.
"""
n = len(t)
if n < 2:
return t
else:
return triRapideRecRandomise(t, 0, n-1)
[docs]def testTriRapideRandomise():
r""" Comparaison des tris par insertion et tris rapides (naif et randomisé), pour des tableaux à :math:`1000` éléments.
Pour le **tri par insertion** :
>>> n = 1000
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> avant = time.time()
>>> _ = triInsertion(t1) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("Un triInsertion: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Un triInsertion: n = 1000, 69.7 milli-secondes.
>>> avant = time.time()
>>> _ = triInsertion(t2) # doctest: +ELLIPSIS
>>> _ = triInsertion(t2) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("Deux triInsertion: n = {}, {:.3g} milli-secondes (presque le meme temps).".format(n, deltaT))
Deux triInsertion: n = 1000, 186 milli-secondes (presque le meme temps).
Pour le **tri rapide naïf** :
>>> n = 1000
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> avant = time.time()
>>> _ = triRapide(t1) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("Un triRapide: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Un triRapide: n = 1000, 4.57 milli-secondes.
>>> t = tabAlea(n)
>>> avant = time.time()
>>> _ = triRapide(t2) # doctest: +ELLIPSIS
>>> _ = triRapide(t2) # doctest: +SKIP
>>> deltaT = 1000 * (time.time() - avant)
>>> print("Deux triRapide: n = {}, {:.3g} milli-secondes (le double).".format(n, deltaT))
Deux triRapide: n = 1000, 9.67 milli-secondes (le double).
Le **tri rapide randomisé** devrait être meilleur, notamment pour des tableaux déjà triés (ou presque triés), vérifions ça :
>>> n = 1000
>>> np.random.seed(0) # Meme exemple à chaque fois
>>> t = tabAlea(n)
>>> t1 = t[:]; t2 = t[:] # On copie les tableaux
>>> avant = time.time()
>>> _ = triRapideRandomise(t1) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("Un triRapideRandomise: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Un triRapideRandomise: n = 1000, 5.48 milli-secondes.
>>> avant = time.time()
>>> _ = triRapideRandomise(t2) # doctest: +ELLIPSIS
>>> _ = triRapideRandomise(t2) # doctest: +ELLIPSIS
>>> deltaT = 1000 * (time.time() - avant)
>>> print("Deux triRapideRandomise: n = {}, {:.3g} milli-secondes (moins que le double).".format(n, deltaT))
Deux triRapideRandomise: n = 1000, 9.31 milli-secondes (moins que le double).
"""
pass
# %% Exercice I.3
if __name__ == '__main__':
print("\n\nI.3. Algorithme de selection d'un element de rang donne.")
[docs]def question_3_a():
r""" Réponse à la question 3.a :
Sans coder, on peut expliquer l'algorithme suivant, très naïf :
- on trie le tableau ``t`` (en temps :math:`\mathcal{O}(n \log n))`, en moyenne ou dans tous les cas selon l'algorithme utilisé),
- puis... on renvoie la k-ième valeur du tableau trié !
Cette méthode sera de complexité :math:`\mathcal{O}(n)` en espace et :math:`\mathcal{O}(n \log n)` en temps (ou pire, selon l'algorithme de tri).
"""
pass
[docs]def quickselect(t, k):
r""" Sélection de l'élément de rang ``k`` du tableau ``t``, par une approche semblable au tri rapide.
- J'ai choisi de renvoyer ``p, v``, la position et la valeur de l'élément recherché (donc ``t[p] = v`` de rang ``k``).
On utilise l'algorithme récursif suivant :
- on partitionne (avec :py:func:`partitionRandomise` appliqué à ``(t, 0, n - 1)``),
- puis on obtient la position ``r`` du pivot, et trois cas peuvent arriver :
- ``k = r``, on a fini et on renvoie ``t[r]``,
- ``k < r`` alors on continue de chercher *à gauche*, donc dans ``t[0:r]`` (la syntaxe plus court ``t[:r]`` est autorisée),
- ``k > r`` alors on continue de chercher *à droite*, donc dans ``t[r + 1:n]`` (de même, la syntaxe plus courte ``t[r + 1:]`` est autorisée).
- L'implémentation est donc récursive, et randomisée (car on utilise :py:func:`partitionRandomise`).
Exemples :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]
>>> print(sorted(t1))
[2, 3, 4, 6, 8]
>>> print(quickselect(t1[:], 0))
(0, 2)
>>> print(quickselect(t1[:], 2))
(2, 4)
>>> print(quickselect(t1[:], 4)) # doctest: +SKIP
(4, 8)
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]
>>> print(sorted(t2))
[-1, 2, 3, 4, 6, 8]
>>> print(quickselect(t2[:], 0))
(0, -1)
>>> print(quickselect(t2[:], 3)) # doctest: +SKIP
(3, 4)
>>> print(quickselect(t2[:], 5))
(5, 8)
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n \log(n))` dans le pire des cas, :math:`\mathcal{O}(n)` dans le meilleur cas (une seule partition à faire si on a de la chance).
- Cette implémentation n'utilise pas deux indices ``i`` et ``j`` mais des sous-tableaux, comme ``t[:r]`` si on cherche *à gauche* (il n'y alors pas d'offset à la position renvoyée), et ``t[r + 1:]`` si on cherche *à droite* (mais alors il faut faire attention car il y a un offset à ajouter, à savoir r + 1, à la position renvoyée par l'appel récursif).
"""
n = len(t)
if n == 0:
raise ValueError("Tableau vide (quickselect failed).")
elif n == 1:
return 0, t[0]
# On a au moins deux valeurs
r = partitionRandomise(t, 0, n - 1) # Attention à n - 1 ici !
if r == k:
# On a trouvé la bonne position !
return r, t[r]
elif r > k: # On va chercher à gauche du pivot
p, v = quickselect(t[:r], k)
return p + 0, v # On a pas d'offset dans la position !
elif r < k: # On va chercher à droite du pivot
p, v = quickselect(t[r + 1:], k)
return p + r + 1, v # On a un offset dans la position !
else:
# On ne devrait jamais être dans ce cas là !
raise ValueError("Erreur, ce cas ne devrait pas arriver !")
# %% Exercice I.4
if __name__ == '__main__':
print("\n\nI.4. Tri par fusion.")
[docs]def insereFusion(x, t):
r""" Insère l'élément ``x`` dans le tableau *trié* ``t``, implémentation naïve (**itérative**).
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n)` dans tous les cas.
- Exemples :
>>> t = [1, 2, 4, 5]
>>> x = -1993; print(insereFusion(x, t)) # Tout a gauche
[-1993, 1, 2, 4, 5]
>>> x = 3; print(insereFusion(x, t)) # Au milieu
[1, 2, 3, 4, 5]
>>> x = 666; print(insereFusion(x, t)) # Tout a droite
[1, 2, 4, 5, 666]
"""
if t == []:
return [x]
else:
i = 0
while i < len(t) and x > t[i]:
i += 1
return t[:i] + [x] + t[i:]
return t # Done
[docs]def fusion(tg, td):
r""" Réalise la fusion des deux tableaux *triés* ``tg`` et ``td``, implémentation naïve **récursive**.
"""
if tg == []:
return td
elif td == []:
return tg
else:
return fusion(tg[1:], insereFusion(tg[0], td))
# return sorted(tg + td) # Done
[docs]def triFusion(t):
r""" Tri fusion pour le tableau ``t`` (de taille :math:`n`).
- Complexité en *espace* : :math:`\mathcal{O}(n \log(n))`.
- Complexité en *temps* : :math:`\mathcal{O}(n \log(n))` dans tous les cas.
- Conclusion : **sous-quadratique**, "en n log n".
Exemples (avec des tableaux de 5 ou 6 éléments) :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]
>>> t1_trie = triFusion(t1)
>>> print(t1_trie)
[2, 3, 4, 6, 8]
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]
>>> t2_trie = triFusion(t2)
>>> print(t2_trie)
[-1, 2, 3, 4, 6, 8]
- Référence : `Tri fusion, sur Wikipédia <https://fr.wikipedia.org/wiki/Tri_fusion>`_, `sur www.sorting-algorithms.com (merge-sort) <http://www.sorting-algorithms.com/merge-sort>`_.
"""
n = len(t)
if n <= 1:
return t
else:
milieu = n // 2
tg = triFusion(t[:milieu])
td = triFusion(t[milieu:])
return fusion(tg, td)
# return sorted(t) # Done
#: Valeur spéciale pour la *"sentinelle"*, :math:`s = +\infty =` ``np.inf``
#: (on utilise la valeur spéciale ``np.inf`` de la bibliothèque Numpy).
sentinelle = +np.inf
[docs]def fusion2(t, tAux, i, milieu, j):
r""" Réalise la fusion des deux tableaux ``tg`` :math:`= [t_i,\dots,t_{\text{milieu}}]` et ``td`` :math:`= [t_{\text{milieu} + 1},\dots,t_i]`.
- On commencera par recopier les deux sous-tableaux dans ``tAux``, en utilisant deux valeurs ``sentinelle`` pour les séparer.
- Ensuite on recopie **sur place** dans ``t`` dans le bon ordre.
- Utilise ce tableau auxiliaire ``tAux`` pour être plus efficace en mémoire.
.. note:: Le sujet demandait ``i, j, k`` mais c'est plus clair avec ``i, milieu, j`` je trouve.
"""
global sentinelle
# 1. Recopiage dans tAux
# tg = [t_i, ..., t_{milieu}]
for position in range(i, milieu + 1):
tAux[position - i] = t[position]
# Première sentinelle
tAux[milieu + 1 - i] = sentinelle
# td = [t_{milieu + 1}, ..., t_j]
for position in range(milieu + 1, j + 1):
tAux[position + 1 - i] = t[position]
tAux[j + 1 - i] = sentinelle
# 2. Ré-écriture dans t
position_d = 0
position_g = milieu + 2 - i
# On cherche à remplir t[i:j + 1] = [t[i], .., t[j]] :
for position in range(i, j + 1):
if tAux[position_g] <= tAux[position_d]:
# Valeur de gauche plus petite que celle de droite
if tAux[position_g] < sentinelle:
# Si ce n'est pas encore la sentinelle, on empile
t[position] = tAux[position_g]
position_g += 1
else:
pass # On est au bout
else:
# Valeur de gauche plus droite que celle de gauche
if tAux[position_d] < sentinelle:
# Si ce n'est pas encore la sentinelle, on empile
t[position] = tAux[position_d]
position_d += 1
else:
pass # On est au bout
# Fin.
[docs]def triFusionRec2(t, tAux, i, j):
r""" Fonction récursive qui trie le sous tableau :math:`[t_i,\dots,t_j]` en le découpant en deux et en triant récursivement les deux sous-tableaux, puis utilise :py:func:`fusion2` pour recoller.
- Utilise ce tableau auxiliaire ``tAux`` pour être plus efficace en mémoire.
- *Attention*: La fusion est faite dans cette fonction, et pas dans la suivante :py:func:`triFusion2`.
"""
n = j - i + 1
# return False
if n > 1:
milieu = (i + j) // 2
triFusionRec2(t, tAux, i, milieu)
# Le pivot t[milieu] est dans le tableau de droite td.
triFusionRec2(t, tAux, milieu + 1, j)
fusion2(t, tAux, i, milieu, j)
# return sorted(t[i:j]) # Done
[docs]def triFusion2(t):
r""" Version optimisée en mémoire du tri fusion, **en place**.
- Complexité en *espace* : :math:`\mathcal{O}(n)` (plus économique que la version naïve :py:func:`triFusion`).
- Complexité en *temps* : :math:`\mathcal{O}(n \log(n))` dans tous les cas.
- Conclusion : **sous-quadratique**, "en n log n".
Exemples (avec des tableaux de 5 ou 6 éléments) :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]
>>> triFusion2(t1)
>>> print(t1) # doctest: +SKIP
[2, 3, 4, 6, 8]
- Avec 6 éléments :
>>> t2 = [4, 2, 3, 6, 8, -1]
>>> triFusion2(t2)
>>> print(t2) # doctest: +SKIP
[-1, 2, 3, 4, 6, 8]
- Référence : `Tri fusion, sur Wikipédia <https://fr.wikipedia.org/wiki/Tri_fusion>`_, `sur www.sorting-algorithms.com (merge-sort) <http://www.sorting-algorithms.com/merge-sort>`_.
"""
n = len(t)
if n <= 1:
return t
else:
tAux = [sentinelle] * (n + 2)
return triFusionRec2(t, tAux, 0, n - 1)
# %% Exercice I.5
if __name__ == '__main__':
print("\n\nI.5. Tri par comptage.")
[docs]def comptage(t, m):
r""" Calcul des **effectifs** du tableau ``t``, dont toutes les valeurs sont entières, entre ``0`` et ``m`` (bornes incluses), en temps et mémoire :math:`\mathcal{O}(\max(len(t), m))`.
Exemples :
- Avec un petit tableau, et ``m = 4`` :
>>> t = [1, 2, 1, 4, 1]
>>> print(comptage(t, 4))
[0, 3, 1, 0, 1]
- Avec un tableau de 1000 valeurs, toutes entre 1 et 10 :
>>> random.seed(0) # Meme exemple à chaque fois
>>> t = [random.randrange(1, 11) for _ in range(1000)]
>>> print(comptage(t, 10))
[0, 114, 87, 95, 102, 110, 89, 109, 104, 86, 104]
.. note:: On l'a déjà implémenté, dans `le TP2 (fonction effectifs) <TP2.html#effectifs>`_, fin septembre !
"""
# On vérifie, juste au cas où
assert all(0 <= i <= m for i in t), "Une valeur du tableau t n'est pas comprise entre 0 et m (not (0 <= i <= m))."
e = [0] * (m + 1)
for i in t:
e[i] += 1
return e
[docs]def triComptage(t, m):
r""" Tri par comptage pour le tableau ``t`` (de taille :math:`n`), à valeurs entières toutes entre ``0`` et ``m``.
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n)` **dans tous les cas**.
- Conclusion : **linéaire**. *Wait, what?!*
.. attention:: Un algorithme de tri *en temps linéaire* ? **Mais COMMENT ?**
Vous avez peut-être entendu parler d'un résultat classique : `"tout algorithme de tri est au mieux en O(n log n)" <https://fr.wikipedia.org/wiki/Algorithme_de_tri#Complexit.C3.A9_algorithmique>`_.
Et bien en fait, c'est faux, dit comme ça, il ne faut pas oublier de préciser "tout algorithme de tri **GÉNÉRIQUE** et **basé sur des comparaisons**" est *au mieux* en :math:`\mathcal{O}(n \log n)` (on écrit alors :math:`\Omega(n \log n)`).
Ce tri par comptage n'est **pas basé sur des comparaisons**, mais il n'est **pas générique** (il ne marche que pour des tableaux d'entiers bornés par ``m``).
Exemples (avec des tableaux de 5 ou 6 éléments) :
- Avec 5 éléments :
>>> t1 = [4, 2, 3, 6, 8]
>>> t1_trie = triComptage(t1, 8)
>>> print(t1_trie)
[2, 3, 4, 6, 8]
- Avec 6 éléments :
>>> t2 = [4, 2, 4, 6, 8, 6]
>>> t2_trie = triComptage(t2, 8)
>>> print(t2_trie)
[2, 4, 4, 6, 6, 8]
- Référence : `Tri comptage, sur Wikipédia <https://fr.wikipedia.org/wiki/Tri_comptage>`_.
"""
n = len(t)
effectifs = comptage(t, m)
t_trie = [-1] * n
i = 0
for x in range(m + 1):
for _ in range(effectifs[x]):
t_trie[i] = x
i += 1
return t_trie
[docs]def question_5_2_exemple():
r""" **Question 5.2).**
Un exemple de tableau plus complexe, qu'on peut aussi chercher à trier :
>>> t = [(6, "pommes"), (2, "melons"), (3, "kiwis")]
Ce tableau contient des couples :math:`(i, x)`, avec :math:`i \in [| 0, m |]` une clé et :math:`x` un object *"quelconque"* (qu'on sait ordonner, par ``<`` ou ``>``).
Encore une fois, on souhaite trier le tableau ``t``, par ordre croissant des clés.
>>> print(sorted(t))
[(2, 'melons'), (3, 'kiwis'), (6, 'pommes')]
.. attention:: Pas besoin de clés uniques !
On n'a pas besoin de supposer que les clés :math:`i` soient uniques pour le tableau ``t`` !
En fait, le tri comptage est intéressant justement si les clés ne sont pas uniques !
"""
pass
# Meilleure méthode !
[docs]def sommeCumulee(t):
r""" Calcule la somme cumulées des valeurs de t, en :math:`\mathcal{O}(n)` en temps et espace.
- Exemples :
>>> print(sommeCumulee([0, 2, 3, 5]))
[0, 2, 5, 10]
>>> print(sommeCumulee(range(6))) # Nombres triangulaires !
[0, 1, 3, 6, 10, 15]
.. note:: Cette fonction est très courant en statistiques, vous la verrez sûrment sous le dous nom de `cumsum <https://duckduckgo.com/?q=cumsum+function>`_, par exemple dans le module :py:mod:`numpy` : `numpy.cumsum <https://docs.scipy.org/doc/numpy/reference/generated/numpy.cumsum.html>`_.
"""
n = len(t)
# u = t[:] # Une copie fraiche, astuce. On peut aussi utiliser list(t).
u = [t[0]] * n
for i in range(1, n):
u[i] = u[i - 1] + t[i] # On accumule les valeurs
return u
[docs]def effectifsCumules(t, m):
r""" Calcul des **effectifs cumulés** du tableau ``t``, dont toutes les valeurs sont entières, entre ``0`` et ``m``, en temps et mémoire :math:`\mathcal{O}(\mathrm{len}(t) + m) = O(n + m)`.
Exemples :
- Avec un petit tableau, et ``m = 4`` :
>>> t = [1, 2, 1, 4, 1]
>>> print(effectifsCumules(t, 4))
[0, 0, 3, 4, 4]
- Avec un tableau de 1000 valeurs, toutes entre 1 et 10 :
>>> random.seed(0) # Meme exemple à chaque fois
>>> t = [random.randrange(1, 11) for _ in range(1000)]
>>> print(comptage(t, 10))
[0, 114, 87, 95, 102, 110, 89, 109, 104, 86, 104]
>>> print(effectifsCumules(t, 10))
[0, 0, 114, 201, 296, 398, 508, 597, 706, 810, 896]
.. note:: On l'a déjà implémenté, dans `le TP2 (fonction effectifsCumulesOpti) <TP2.html#effectifsCumulesOpti>`_, fin septembre !
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n)`.
"""
e = comptage(t, m)
return [cum - val for cum, val in zip(sommeCumulee(e), e)]
[docs]def triComptageCle(t, m):
r""" Tri par comptage pour le tableau ``t`` (de taille :math:`n`), contenant des couples :math:`(i, x)`, avec :math:`i \in [| 0, m |]` une clé et :math:`x` un object *"quelconque"* (qu'on sait ordonner, par ``<`` ou ``>``).
- Complexité en *espace* : :math:`\mathcal{O}(n)`.
- Complexité en *temps* : :math:`\mathcal{O}(n)` **dans tous les cas**.
- Conclusion : **linéaire**. *Même remarque que précédemment*.
- Exemple :
>>> t = [(6, "pommes"), (2, "melons"), (3, "kiwis")]
>>> t_trie = triComptageCle(t, 6)
>>> print(t_trie)
[(2, 'melons'), (3, 'kiwis'), (6, 'pommes')]
- Référence : `Tri comptage, sur Wikipédia <https://fr.wikipedia.org/wiki/Tri_comptage>`_.
.. note:: Oui, le tri comptage devrait être stable, s'il est bien implémenté.
"""
return sorted(t) # FIXME solution à finir si j'ai le temps
n = len(t)
cles = [i for i, x in t]
# ec = effectifsCumules(cles, m)
ec = comptage(cles, m)
t_trie = [-1] * n
i = 0
# for i, x in t:
for x in range(m + 1):
for _ in range(ec[x]):
t_trie[i] = x
i += 1
return t_trie
# %% 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()
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 TP7.py