TP7 : algorithmes de tris

On s’intéressera aujourd’hui aux algorithmes de tris les plus courants :

• Tri par insertion,
• tri rapide, et tri rapide “randomisé”,
• sélection de l’élément de rang k,
• tri par fusion, deux versions,
• tri par comptage.

Note

“Étudier des tris ? Encore ?”

• Les algorithmes de tris sont des exemples ultra-classiques d’algorithmes “de base” (manipulant des listes ou des tableaux de nombres), qu’il faut bien connaître.
• On ne demande pas d’apprendre par cœur le code d’aucun de ces tris, mais le concept ou l’idée derrière chacun (indice : le nom aide pas mal...).
• Même Barack Obama vous le dira, les algorithmes de tris sont importants ! Démonstration en vidéo :

---

Documentation

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, sur WikiBooks,
• Un petit site permettant la visualisation des différents tris : http://www.sorting-algorithms.com/,
• Algorithmes de tris, sur Wikipédia,
• Comparaison d’algorithmes de tris, aussi sur Wikipédia.

Convention : on dira qu’un tableau t est trié lorsqu’il est trié en ordre croissant, c’est à dire :

\[\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).

TP7.triInsertion(t)

Tri par insertion pour le tableau t (de taille \(n\)).

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\mathcal{O}(n^2)\) dans le pire des cas, \(\mathcal{O}(n)\) dans les meilleurs cas (déjà trié, ou presque trié), et \(\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, sur www.sorting-algorithms.com (insertion-sort).
• Note : le tri par insertion est un tri par comparaison, mais il n’effectue pas d’échange (avec echanger()).
• Cet algorithme de tri, et presque tous les suivants, sont en place : ils modifient le tableau donné en entrée.

TP7.echanger(t, i, j)

Fonction classique, pour échanger t[i] et t[j] en place, c’est très simple en 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) :

def echanger_avec_tmp(t, i, j):
    tmp = t[j]
    t[j] = t[i]
    t[i] = tmp

TP7.partition(t, i, j)

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 \(\mathcal{O}(j - i + 1)\), longueur du sous-tableau manipulé.
• Cette impémentation (voir la source) est l’implémentation impérative “classique”, comme faite en cours.

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 : partitionAvecRecopies().

TP7.partitionAvecRecopies(t, i, j)

Une autre implémentation de la fonction de partition, avec des une recopie sous forme de sous-tableau, ça termine par :

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 partition().

TP7.triRapideRec(t, i, j)

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

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

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

def 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.

TP7.triRapide(t)

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

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

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

• Avec 5 éléments :

>>> 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, sur www.sorting-algorithms.com (quick-sort).

TP7.tabAlea(n)

Utilise numpy.random pour créer un tableau aléatoire de taille n, remplis de nombres flottants uniformément tirés dans \([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)  
[0.5488..., 0.7151..., ...]

TP7.tabAleaEntiers(n)

Utilise numpy.random pour créer un tableau aléatoire de taille n, remplis de nombres entiers uniformément tirés dans \([|-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)  
[716, 591, -363, ..., -1311]

TP7.testTriRapide()

Exemples de tris par insertion et tris rapide de tableaux à \(200\) et \(1000\) éléments (l’énoncé demandait d’aller jusqu’à \(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])  
[0.5488..., 0.7151..., ...]
>>> print(triInsertion(t1)[:3])  
[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])  
[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 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])  
[716, 591, ...]
>>> print(triInsertion(t1)[:3])  
[-1932, -1930, ...]
>>> print(all([x == y for x, y in zip(t1, sorted(t1))]))  # A-t-on trié correctement ?
True
>>> print(triRapide(t2)[:3])  
[-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 timeit.timeit() du module timeit (ou la commande magique %timeit, dans IPython, qui marche très désormais très bien), ou avec la fonction 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)  
>>> 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)  
>>> 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)  
>>> 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)  
>>> 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 triInsertion() est environ 25 (\(= 5^2\)) fois plus grand sur un tableau 5 fois plus grand, tandis que pour triRapide(), l’augmentation est plutôt de l’ordre de 6 (et \(\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 \(\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)  
>>> 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 (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)  
>>> deltaT = time.time() - avant
>>> print("triRapide: n = {}, {:.3g} secondes.".format(n, deltaT))
triRapide: n = 100000, 0.724 secondes.
>>> avant = time.time()
>>> _ = triRapide(t2)  
>>> 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

TP7.partitionRandomise(t, i, j)

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) :

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 partition() (qui utilisait le pivot en première place t[i]).

TP7.triRapideRecRandomise(t, i, j)

Sous-fonction récursive randomisée, utilise la fonction partitionRandomise() pour trier le sous-tableau \([t_i, \dots, t_{j - 1}]\).

TP7.triRapideRandomise(t)

Meilleure version du tri rapide, pour le tableau t (de taille \(n\)).

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\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, sur www.sorting-algorithms.com (quick-sort, again).

TP7.testTriRapideRandomise()

Comparaison des tris par insertion et tris rapides (naif et randomisé), pour des tableaux à \(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)  
>>> 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)  
>>> _ = triInsertion(t2)  
>>> 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)  
>>> 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)  
>>> _ = triRapide(t2)  
>>> 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)  
>>> 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)  
>>> _ = triRapideRandomise(t2)  
>>> 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).

TP7.question_3_a()

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 \(\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é \(\mathcal{O}(n)\) en espace et \(\mathcal{O}(n \log n)\) en temps (ou pire, selon l’algorithme de tri).

TP7.quickselect(t, k)

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 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 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))  
(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))  
(3, 4)
>>> print(quickselect(t2[:], 5))
(5, 8)

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\mathcal{O}(n \log(n))\) dans le pire des cas, \(\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).

TP7.insereFusion(x, t)

Insère l’élément x dans le tableau trié t, implémentation naïve (itérative).

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\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]

TP7.fusion(tg, td)

Réalise la fusion des deux tableaux triés tg et td, implémentation naïve récursive.

TP7.triFusion(t)

Tri fusion pour le tableau t (de taille \(n\)).

• Complexité en espace : \(\mathcal{O}(n \log(n))\).
• Complexité en temps : \(\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, sur www.sorting-algorithms.com (merge-sort).

TP7.sentinelle = inf

Valeur spéciale pour la “sentinelle”, \(s = +\infty =\) np.inf (on utilise la valeur spéciale np.inf de la bibliothèque Numpy).

TP7.fusion2(t, tAux, i, milieu, j)

Réalise la fusion des deux tableaux tg \(= [t_i,\dots,t_{\text{milieu}}]\) et td \(= [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.

TP7.triFusionRec2(t, tAux, i, j)

Fonction récursive qui trie le sous tableau \([t_i,\dots,t_j]\) en le découpant en deux et en triant récursivement les deux sous-tableaux, puis utilise 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 triFusion2().

TP7.triFusion2(t)

Version optimisée en mémoire du tri fusion, en place.

• Complexité en espace : \(\mathcal{O}(n)\) (plus économique que la version naïve triFusion()).
• Complexité en temps : \(\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)  
[2, 3, 4, 6, 8]

• Avec 6 éléments :

>>> t2 = [4, 2, 3, 6, 8, -1]
>>> triFusion2(t2)
>>> print(t2)  
[-1, 2, 3, 4, 6, 8]

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

TP7.comptage(t, m)

Calcul des effectifs du tableau t, dont toutes les valeurs sont entières, entre 0 et m (bornes incluses), en temps et mémoire \(\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), fin septembre !

TP7.triComptage(t, m)

Tri par comptage pour le tableau t (de taille \(n\)), à valeurs entières toutes entre 0 et m.

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\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)”.

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 \(\mathcal{O}(n \log n)\) (on écrit alors \(\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.

TP7.question_5_2_exemple()

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 \((i, x)\), avec \(i \in [| 0, m |]\) une clé et \(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 \(i\) soient uniques pour le tableau t ! En fait, le tri comptage est intéressant justement si les clés ne sont pas uniques !

TP7.sommeCumulee(t)

Calcule la somme cumulées des valeurs de t, en \(\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, par exemple dans le module numpy : numpy.cumsum.

TP7.effectifsCumules(t, m)

Calcul des effectifs cumulés du tableau t, dont toutes les valeurs sont entières, entre 0 et m, en temps et mémoire \(\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), fin septembre !

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\mathcal{O}(n)\).

TP7.triComptageCle(t, m)

Tri par comptage pour le tableau t (de taille \(n\)), contenant des couples \((i, x)\), avec \(i \in [| 0, m |]\) une clé et \(x\) un object “quelconque” (qu’on sait ordonner, par < ou >).

• Complexité en espace : \(\mathcal{O}(n)\).
• Complexité en temps : \(\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.

Note

Oui, le tri comptage devrait être stable, s’il est bien implémenté.

---

Bonus : un tri stupide ?

En bonus, je vous laisse étudier (et implémenter) cet algorithme de tri, mon préféré (mais pas le plus efficace) :

Entrée : Tableau de nombres réels T, de taille n
1. Tant que T n'est pas trié:
2.    Mélanger T
Sortie : Tableau T, trié.

Questions :

1. L’algorithme termine-t-il ? Sur toutes les entrées ? Sur aucune entrée ?
2. L’algorithme est-il déterministe ou probabiliste ? S’il est probabiliste, peut-il ne jamais terminer (si oui, avec quelle probabilité ?)
3. Estimer la complexité optimale de l’étape 1 (vérifier si T est trié), et de l’étape 2 (mélanger T). Astuce / rappel : générer une permutation aléatoire \(\sigma \in \Sigma_n\) prend un temps \(O(n)\) (l’algorithme n’est pas évident, mais c’est possible).
4. Estimer le nombre moyen (probabiliste) de parcours de la boucle “Tant que”, pour un tableau quelconque (tiré dans un certain univers \(\Omega\) à préciser).
5. Conclure quant à la complexité en moyenne de ce tri (“tri par mélanges répétés”).
6. Est-ce un algorithme optimal ? Presque optimal ? Pour tout tableau ? Pour presque tout tableau ?
7. Ou bien est-ce l’algorithme le plus stupide auquel on peut penser ... ?!

---

Sortie du script

Note

Les docstrings foirent un peu, à cause de mesures de temps d’execution qui sont hautement aléatoires, et de l’aléa utilisé dans les tests.

$ python TP7.py


I.1. Tri par insertion.


I.2. Tri rapide.


I.3. Algorithme de selection d'un element de rang donne.


I.4. Tri par fusion.


I.5. Tri par comptage.
Test automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :
**********************************************************************
File "TP7.py", line 375, in __main__.testTriRapide
Failed example:
    print("triInsertion: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    triInsertion: n = 200, 2.71 milli-secondes.
Got:
    triInsertion: n = 200, 2.62 milli-secondes.
**********************************************************************
File "TP7.py", line 380, in __main__.testTriRapide
Failed example:
    print("triRapide: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    triRapide: n = 200, 0.772 milli-secondes.
Got:
    triRapide: n = 200, 0.665 milli-secondes.
**********************************************************************
File "TP7.py", line 393, in __main__.testTriRapide
Failed example:
    print("triInsertion: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    triInsertion: n = 1000, 57.3 milli-secondes.
Got:
    triInsertion: n = 1000, 42.5 milli-secondes.
**********************************************************************
File "TP7.py", line 398, in __main__.testTriRapide
Failed example:
    print("triRapide: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    triRapide: n = 1000, 4.74 milli-secondes.
Got:
    triRapide: n = 1000, 2.07 milli-secondes.
**********************************************************************
File "TP7.py", line 416, in __main__.testTriRapide
Failed example:
    print("triRapide: n = {}, {:.3g} secondes.".format(n, deltaT))
Expected:
    triRapide: n = 20000, 0.128 secondes.
Got:
    triRapide: n = 20000, 0.0586 secondes.
**********************************************************************
File "TP7.py", line 431, in __main__.testTriRapide
Failed example:
    print("triRapide: n = {}, {:.3g} secondes.".format(n, deltaT))
Expected:
    triRapide: n = 100000, 0.724 secondes.
Got:
    triRapide: n = 100000, 0.342 secondes.
**********************************************************************
File "TP7.py", line 436, in __main__.testTriRapide
Failed example:
    print("Python's builtin sorted: n = {}, {:.3g} secondes.".format(n, deltaT))
Expected:
    Python's builtin sorted: n = 100000, 0.721 secondes.
Got:
    Python's builtin sorted: n = 100000, 0.341 secondes.
**********************************************************************
File "TP7.py", line 522, in __main__.testTriRapideRandomise
Failed example:
    print("Un triInsertion: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    Un triInsertion: n = 1000, 69.7 milli-secondes.
Got:
    Un triInsertion: n = 1000, 32.3 milli-secondes.
**********************************************************************
File "TP7.py", line 528, in __main__.testTriRapideRandomise
Failed example:
    print("Deux triInsertion: n = {}, {:.3g} milli-secondes (presque le meme temps).".format(n, deltaT))
Expected:
    Deux triInsertion: n = 1000, 186 milli-secondes (presque le meme temps).
Got:
    Deux triInsertion: n = 1000, 30.5 milli-secondes (presque le meme temps).
**********************************************************************
File "TP7.py", line 541, in __main__.testTriRapideRandomise
Failed example:
    print("Un triRapide: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    Un triRapide: n = 1000, 4.57 milli-secondes.
Got:
    Un triRapide: n = 1000, 2.01 milli-secondes.
**********************************************************************
File "TP7.py", line 548, in __main__.testTriRapideRandomise
Failed example:
    print("Deux triRapide: n = {}, {:.3g} milli-secondes (le double).".format(n, deltaT))
Expected:
    Deux triRapide: n = 1000, 9.67 milli-secondes (le double).
Got:
    Deux triRapide: n = 1000, 2.17 milli-secondes (le double).
**********************************************************************
File "TP7.py", line 561, in __main__.testTriRapideRandomise
Failed example:
    print("Un triRapideRandomise: n = {}, {:.3g} milli-secondes.".format(n, deltaT))
Expected:
    Un triRapideRandomise: n = 1000, 5.48 milli-secondes.
Got:
    Un triRapideRandomise: n = 1000, 3.94 milli-secondes.
**********************************************************************
File "TP7.py", line 567, in __main__.testTriRapideRandomise
Failed example:
    print("Deux triRapideRandomise: n = {}, {:.3g} milli-secondes (moins que le double).".format(n, deltaT))
Expected:
    Deux triRapideRandomise: n = 1000, 9.31 milli-secondes (moins que le double).
Got:
    Deux triRapideRandomise: n = 1000, 5.39 milli-secondes (moins que le double).
**********************************************************************
2 items had failures:
   7 of  65 in __main__.testTriRapide
   6 of  39 in __main__.testTriRapideRandomise
***Test Failed*** 13 failures.

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

Le fichier Python se trouve ici : TP7.py.