C1-ALGO-05.02 Algorithmes classiques (Tri)

Objectifs pédagogiques :

• comprendre ce qu’est le tri en algorithmique

• connaître quelques algorithmes de tri classiques

Introduction

L’une des classes d’algorithmes les plus courants sont ceux qui permettent de trier des objets. On utilise généralement un ordre numérique (du plus petit au plus grand) ou lexicographique (de la lettre A à la lettre Z)

Les deux principales caractéristiques qui permettent de distinguer les différents algorithmes de tri sont la complexité temporelle (combien de temps faut-il pour trier une liste ?) et la complexité spatiale (combien de mémoire ai-je besoin pour trier une liste ?)

Exemple introductif

Voici une liste de nombres entier qu’il faut trier du plus petit au plus grand :

[23,45,14,9,245,56,81,11,6]

Décrivez votre méthode (votre algorithme) à l’aide d’un algorigramme

Exemple introductif 2

Voici une liste de mot qu’il s’agit de trier comme un dictionnaire:

zoologie
alphabet
romain
fusain
wagon
locomotive
largeur
romantique
Rome
Antique
fusée

Décrivez votre méthode (votre algorithme) à l’aide d’un algorigramme

Tri par sélection (Selection Sort)

C’est la méthode la plus naïve. On parcourt la liste de n élément, on cible le plus grand que l’on place en dernière position. Puis on parcourt la liste de n-1 éléments, on cible le plus grand restant que l’on place en avant-dernière position et ainsi de suite.

C’est un algorithme lent

from IPython.display import YouTubeVideo

YouTubeVideo('92BfuxHn2XE', width=960, height=540)

Tri à bulles (Bubble Sort)

Le tri à bulles consiste à parcourir la liste de n éléments et de comparer chaque élément consécutif et à les permuter s’ils ne sont pas triés correctement.

C’est un algorithme lent.

from IPython.display import YouTubeVideo

YouTubeVideo('Cq7SMsQBEUw', width=960, height=540)

Tri par insertion (Insertion Sort)

C’est la méthode de tri utilisée généralement pour classer ses cartes à jouer.

Le tri par insertion considère chaque élément du tableau de n éléments et l’insère à la bonne place dans les éléments déjà triés. Ainsi, au moment de l’insertion, on considère que tous les éléments plus petits sont correctement triés.

C’est un algorithme lent

from IPython.display import YouTubeVideo

YouTubeVideo('8oJS1BMKE64', width=960, height=540)

Tri rapide (Quick Sort)

La méthode consiste à placer un élément du tableau (le pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui sont supérieurs au pivot soient à sa droite. Le pivot est choisi aléatoirement (au hasard)

Cette opération s’appelle partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l’opération de partitionnement. Ce processus est répété récursivement, jusqu’à ce que l’ensemble des éléments soit trié.

Concrètement, pour partitionner un sous-tableau :

• le pivot est placé à la fin (arbitrairement), en l’échangeant avec le dernier élément du sous-tableau ;

• tous les éléments inférieurs au pivot sont placés en début du sous-tableau ;

• le pivot est déplacé à la fin des éléments déplacés.

C’est un algorithme rapide (et qui peut être exécuté en parallèle)

from IPython.display import YouTubeVideo

YouTubeVideo('8hEyhs3OV1w', width=960, height=540)

Tri Fusion (Merge Sort)

C’est un tri dichotomique. On peut le décrire par :

L’algorithme est naturellement décrit de façon récursive.

1. Si le tableau n’a qu’un élément, il est déjà trié.

2. Sinon, séparer le tableau en deux parties à peu près égales.

3. Trier récursivement les deux parties avec l’algorithme du tri fusion.

4. Fusionner les deux tableaux triés en un seul tableau trié.

C’est un algorithme rapide

from IPython.display import YouTubeVideo

YouTubeVideo('ZRPoEKHXTJg', width=960, height=540)

Comparaison des complexités temporelles des méthodes de tri

Dans le tableau suivant, sont listées les complexités computationnelles des différentes méthodes de tri. Il s’agit là du nombre d’opérations nécessaires pour effectuer un tri dans le cas optimal, le cas moyen et le pire des cas.

Méthode de tri	Cas optimal	Cas moyen	Pire des cas
Tri par sélection	\(n^2\)	\(n^2\)	\(n^2\)
Tri par insertion	\(n\)	\(n^2\)	\(n^2\)
Tri à bulle	\(n\)	\(n^2\)	\(n^2\)
Tri Fusion	\(n~log(n)\)	\(n~log(n)\)	\(n~log(n)\)
Tri Rapide	\(n~log(n)\)	\(n~log(n)\)	\(n^2\)

Classification des algorithmes de tri

Suivant le problème à résoudre, il s’agit de choisir un algorithme de tri. Ce choix est basé sur les différentes caractéristiques des algorithmes de tri et des besoins du problème (ou de son résultat)

• complexité temporelle

• complexité spatiale

• stabilité : est-ce que l’ordre d’entrée est respecté à la sortie de l’algorithme ?

Il existe d’autres caractéristiques qui n’entrent pas dans le cadre de ce cours d’introduction.

Comparaison des différents algorithmes de tri sur des situations différentes

from IPython.display import YouTubeVideo

YouTubeVideo('ZZuD6iUe3Pc', width=960, height=540)