Algorithmes de tri


Les tris sont des opérations très fréquentes en informatique : tri lexicographique (annuaires), tri de requêtes (par prix sur des sites commerciaux par exemple), tri par pertinence (moteurs de recherche)…

Stratégies de tri
Une stratégie particulièrement efficace est la stratégie « diviser pour régner ». Cette stratégie a été rencontrée en 1ère année lors de la recherche dichotomique d’un élément dans un tableau préalablement trié (nous y voilà), lors de la recherche dichotomique du zéro d’une fonction et cette année avec la méthode récursive d’exponentiation rapide.
Les deux derniers algorithmes de tri proposés reposent sur cette méthode et sont récursifs.

Dans toute la suite, il s'agit de trier par ordre croissant un tableau de nombres.

Tri par insertion

Principe du tri par insertion

En résumé, on trie une sous-liste constituée de 2 éléments dont 1 est trié puis on trie une sous-liste constituée de 3 éléments dont 2 sont triés, etc.

Etape 1 : 1 élément trié Tri insertion étape 1

Etape 2 : 2 éléments triés Tri insertion étape 2

Etape 3 : 3 éléments triés Tri insertion étape 3

Etape 4 : 4 éléments triés Tri insertion étape 4

De l'étape i à l'étape i+1, on trie une sous-liste (en bleu) dont les i premiers éléments sont triés (en vert), on ne positionne donc qu'un seul élément à chaque étape dans cette sous-liste d'éléments déjà triés.

A - Approche modulaire

La vidéo ci-dessus met en évidence des étapes esentielles du tri par insertion :
1/ la recherche de la position (index dans le tableau) de l'élément à insérer ;
2/ le décalage de certains éléments.

Dans une première approche, ces différentes tâches vont être confiées à autant de fonctions.

A-1/ Recherche de la position d'insertion

Hypothèse : on envisage une liste L dont tous les éléments sont triés par ordre croissant sauf le dernier.

Exemple
   L = [1,3,5,2] : la liste comporte 4 éléments, les 3 premiers éléments sont bien classés par ordre croissant.

Exercice - Ecrire une fonction indexPlace(L:list)->int renvoyant la position (l'index) à laquelle le dernier élément devrait se trouver dans la liste L (en imaginant que les éléments suivants devraient être décalés vers la droite) pour qu'elle soit entièrement triée.

Exemple
   Avec L = [1,3,5,2] la fonction indexPlace(L) renvoie 1 : la liste L, si elle était classée, devrait commencer par [1, 2,...].

Conseil : utiliser une boucle while dont le compteur, noté j, est décroissant.

Tests : tester la fonction dans différents cas (élément à insérer au début, à la fin, au "milieu") : L = [1,3,5,0], L = [1,3,5,7], L = [1,3,5,2].


A - 2/ Décalage des éléments

Hypothèse : la liste L est triée sauf son dernier élément.

Exemple
   L = [1,3,5,2].

Exercice - Ecrire une fonction decale(L:list, d:int, f:int)->list où L est une liste, d et f des entiers tels que d < f.
A partir de l'index final f et jusqu'à l'index de départ d, la fonction recopie chaque élément dans la case suivante (autrement dit, la liste est parcourue de droite à gauche).
A l'issue de l'opération, les éléments de la liste sont modifiés.

Exemple
   Avec L = [1,3,5,2] la fonction decale(L,1,3) renvoie [1, 3, 3, 5].

Tester la fonction.


A - 3/ Etape finale - Tri par insertion version modulaire

Exercice - Ecrire une fonction tri_insertion_mod(L:list)->list renvoyant la liste L triée par ordre croissant. Cette fonction utilisera les fonctions précédentes.

Tester la fonction.


Pour tester la fonction, on pourra importer le module random puis construire une liste de longueur aléatoire constituée de valeurs aléatoires.
Rappel : from random import randint puis randint(a,b) renvoie un nombre a ≤ n ≤ b.

B - Approche progressive

Dans cette approche, on va modifier progressivement la fonction initiale (indexPlace) pour aboutir à la fonction souhaitée.

B - 1/ Modification d'une fonction existante

Hypothèse : la liste L est triée sauf son dernier élément.

Exemple
   L = [1,3,5,2].

Exercice - Ecrire une fonction place(L:list)->list renvoyant la liste L triée par ordre croissant.
Les éléments plus grands que le dernier élément (noté e) sont décalés vers la droite puis l'élément e est inséré à la place qu'il doit occuper. Cette fonction sera construite par ajouts ou modifications de code à partir du code de indexPlace, elle n'appellera aucune des fonctions précédentes.
Cette fonction profite de la recherche de l'index pour effectuer simultanément les décalages et se termine par l'insertion.

Tester la fonction.


B - 2/ Tri par insertion version progressive

Exercice - Ecrire une fonction tri_insertion_prog(L:list)->list renvoyant la liste L triée par ordre croissant.
Cette fonction sera déduite de la fonction place(L) par ajout de code et n'appellera aucune des fonctions précédentes.

Tester la fonction.


Tri rapide (Quick sort)

Principe du tri rapide

Il s'agit d'un tri récursif dichotomique (méthode "diviser pour régner") d'un tableau T :

  1. On partitionne le tableau T autour d'un pivot (élément de T choisi aléatoirement) : on constitue un tableau Tinf de valeurs inférieures au égales au pivot (sans chercher à trier ces valeurs), suivi du pivot qui se trouve à sa place définitive, suivi d'un tableau Tsup de valeurs strictement supérieures au pivot.
  2. On itère le procédé sur chacun des deux sous-tableaux Tinf et Tsup (jusqu'à ce qu'ils ne contiennent plus qu'un seul élément).

Exemple : le pivot est le premier élément de la liste en cours de traitement.

Etape 1 : Tri insertion étape 1 Puis la fonction s'appelle elle-même pour trier les deux tableaux Tinf = [3,1,4,2] et Tsup = [8].

Etape 2 : Tinf et Tsup (déjà trié ici) sont triés sur le même principe Tri insertion étape 2 Et ainsi de suite.

A chaque étape, un tri partiel est effectué, seul un élément (le pivot, en rouge) est trié (i.e. les autres éléments sont répartis de part et d'autre du pivot).
A chaque étape, la liste transformée est la forme : [éléments plus petits que le pivot] + [pivot] + [éléments plus grands que le pivot].

A la fin des appels récursifs, le liste initiale est découpée en listes composées d'un unique élément mais ces éléments sont classés les uns par rapport aux autres, et la liste complète est reconstituée lors de la phase de "remontée" lorsque les sous-listes de l'étape i+1 sont transmises à l'étape i.

Algorithme

Dans la suite, on présente une version destinée aux listes :
- pop, remove, append, techniques de slicing… disponibles ;
- Rappel : la concaténation des listes L1 et L2 s’effectue par L1 + L2.

Remarque :
   Il existe plusieurs versions de ce tri qui diffèrent selon :
   - la méthode utilisée pour choisir le pivot (aléatoire ou non) ;
   - le type de tableau en argument : liste (fonctions dédiées aux listes licites) ou tableau (pas de fonctions spécifiques) ;
   - le détail même de l’algorithme.

Le tableau T est trié récursivement :
- si T est vide ou admet un unique élément, il est trié (critère d’arrêt) : la fonction renvoie T ;
- sinon un tri partiel est effectué par rapport au pivot :
   a/ on choisit un élément de T, appelé pivot, qu’on retire de T ;
   b/ on construit un sous-tableau Tinf constitué des éléments plus petits que le pivot ;
      on construit un sous-tableau Tsup constitué des éléments plus grands que le pivot ;
   c/ le résultat est la concaténation de Tinf récursivement trié, du pivot et de Tsup récursivement trié (i.e. la fonction s’appelle elle-même pour effectuer le tri récursif).

Comprendre : les étapes a/ et b/ correspondent à la dichotomie, l’étape c/ correspond au tri partiel.

Programme

Écrire la fonction tri_rapide(t:list)->list en choisissant comme pivot le dernier élément du tableau t (on pourra utiliser la méthode pop( )).
Tester la fonction.


Exercices (après avoir entièrement terminé le TP)

  • Ecrire une fonction tri_rapide1(t:list)->list en choisissant comme pivot le premier élément du tableau.
  • Ecrire une fonction tri_rapideA(t:list)->list dans laquelle le pivot est choisi aléatoirement (Rappel : from random import randint puis randint(a,b) renvoie un nombre a ≤ n ≤ b).

Tri fusion (Merge sort)

Il s'agit d'un tri récursif dichotomique (méthode "diviser pour régner") d'un tableau T.

Remarque : il existe plusieurs versions de ce tri.

Préliminaires : fusion ou interclassement de deux tableaux triés

On considère deux tableaux T1 et T2 supposés triés.
L'opération de fusion ou interclassement consiste à construire un tableau T, trié, à partir des valeurs de T1 et T2.

Algorithme récursif de fusion

Si T1 est vide alors T2 est renvoyé puisque déjà trié et réciproquement (critères d’arrêt).
Sinon, on effectue un tri partiel :
- on sélectionne le plus petit élément e parmi les deux tableaux T1 et T2 (triés) ;
- on renvoie le tableau constitué de e et de la fusion d’un tableau diminué de cet élément et du tableau intact (appel récursif).

Sur une feuille, illustrer le principe de cet algorithme à l'aide d'un exemple : choisir deux listes triées et donner le résultat de la fusion de ces deux listes.

Programme

Écrire une fonction fusion(t1:list, t2:list)->list qui fusionne récursivement les tableaux triés t1 et t2.
Tester la fonction.


Exercice (après avoir entièrement terminé le TP)

Ecire une version itérative de l'algorithme de fusion.


Algorithme du tri fusion

Principe du tri fusion

Il reste à écrire la fonction tri_fusion (récursive) qui réalise les dichotomies successives puis le tri grâce à la fonction fusion.

Si T est vide ou admet un unique élément, il est trié (critère d’arrêt).
Sinon :
- le tableau T est coupé en deux sous-tableaux T[0 : m] et T[m :] (où m = len(T)//2), étape de dichotomie ;
- on fusionne étape de tri partiel (fonction ci-dessus) les deux sous-tableaux triés récursivement (appel récursif à tri_fusion).

La fonction tri_fusion découpe le tableau de départ en singletons qui sont ensuite fusionnés (et donc triés) peu à peu lors de la phase de remontée.

Sur une feuille, illustrer le principe de cet algorithme en s'inspirant de ce qui a été fait dans le cas du tri rapide.

Programme

Écrire une fonction tri_fusion(t:list)->list.
Tester la fonction.


Complexité

Retenir (résultats admis).

Tri insertionTri rapideTri fusion
AlgorithmeItératifRécursifRécursif
StratégieDiviser pour régner
Complexité spatialeEn placeMémoire supplémentaire (*)
Complexité temporelleAu pire\(O(n^2)\)\(O(n^2)\)\(O(n\;ln(n))\)
Moyenne\(O(n^2)\)\(O(n\;ln(n))\)\(O(n\;ln(n))\)

(*) La gestion de la mémoire dans ces versions naïves n’est pas optimale (l’allocation de mémoire à chaque appel ralentit beaucoup ces algorithmes, il est plus efficace d’allouer une fois pour toute un tableau de taille n et de passer ce tableau en argument).

Meilleure complexité temporelle moyenne : \(O(n\;ln(n))\).