Code source de TP7

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