Diviser pour régner

Divide and conquer – Page Wikipedia

Principe

Il s'agit d'une technique pour créer des algorithmes efficaces en terme de temps de calcul. Un algorithme diviser pour régner suit les étapes suivantes :

Diviser : le problème est découper en sous-problèmes plus petits.
Régner : chaque sous problème est résolu. Éventuellement, leur résolution peur occasionner de nouvelles divisions, récursivement.
Combiner : Calculer la solution du problème en utilisant les solutions des sous-problèmes.

Le nom a quelque chose de publicitaire. Il évoque une stratégie militaire. Il ne fait pas trop le prendre au pied de la lettre : Dans cet algorithme, certes on divise des problèmes, mais “régner” ne veut pas dire grand chose.

Exemple : Le tri

On doit trier un paquet de n items dans l'ordre croissant.

Tri classiques

On trie tout le paquet d'un coup. Je rappelle deux exemples de ces genre de tri – vus en première.

Tri par sélection
Consiste à chercher dans tout le paquet le plus petit élément, le mettre à la suite de ce qu'on a déjà trié, puis recommencer à chercher le plus éléments du paquet pas encore trié.
Tri par insertion
Consiste à prendre les items du paquet à trier comme ils viennent, puis à chercher leur place parmi les items déjà triés.

Ces deux algorithmes on une complexité en $n^2$. Cela veut dire que l'on a – en gros – l'évolution suivante :

$n$	1	10	100	1000	10 000
temps de calcul	1	100	10 000	1 000 000	100 000 000

Si on décuple (x10) le nombre d'items $n\to 10\,n$, le temps de calcul est – en gros – multiplié par 100 : $n^2 \to 100\,n^2$.

Tri par fusion

Le tri par fusion consiste à couper le paquet à trier en deux parts égales (ou à peu près), à trier chacun des deux demi-paquets à part, puis à rassembler les deux-demi paquets en maintenant le tout dans l'ordre.

On reconnaît ici le principe diviser pour régner :

Diviser : Couper le paquet en deux
Régner : Chaque sous paquet est trié
Combiner : On fusionne les deux sous-paquets triés

Cet algorithme a une complexité en $n\log_2(n)$. Si vous n'êtes pas à l'aise avec $\log_2$, dites vous simplement que c'est une fonction qui augmente de 1. Quand $n$ est multiplié par 10, $\log_2(n)$ est augmenté d'environ 3,3. Pour vous faire une idée, plus facilement voici l'évolution de $n\log_2(n)$ :

$n$	1	10	100	1000	10 000
$n\log_2(n)$	0	33	660	9 900	132 000

L'efficacité du tri par fusion est tout à fait remarquable.

Nous nous concentrons ici sur l'efficacité temporelle. Sur cette liste des algorithmes de tri, vous pouvez constater que les différents algorithmes ont aussi une complexité spatiale. Cela représente leur coût en espace mémoire. Vous pouvez voir que le tri par fusion est efficace en temps, mais qu'il occupe beaucoup plus de mémoire.

D'autres algorithmes comme le tri rapide – que nous allons étudier – ou encore mieux le tri par tas, ont à la fois une bonne efficacité temporelle et une bonne efficacité spatiale.

Pour info, l'algorithme de tri utilisé dans la fonction sort de Python est l'algorithme timsort qui est un hybride entre le tri par fusion et le tri par insertion. Notez également que ces fonctions intégrées dans Python exploitent des programmes écrits dans des langages plus rapides, comme C. Vous ne pouvez pas espérer aller plus plus vite en programmant en pur Python.

Quelques exemples

Comparaison de performances

Quand vous aurez produit les fichiers tri_rapide.py et tri_fusion.py vous pourrez utiliser le fichier performances_tri.py – à placer dans le même répertoire que les deux autres – pour comparer les performances des différents tris.

Essayez avec en variant la taille des tableaux : N = 10 puis 100 et 1000.

Au delà de 10 000, le tri par sélection devient très très lent. Si vous voulez poursuivre la comparaison sur des valeurs plus élevées, mieux vaut désactiver le test sur le tir par sélection !