Cours algorithmique trouver et trier

Algorithmes plus efficaces :

Diviser pour régner
Diviser pour régner
Du latin « Divide ut imperes » (Machiavel)
On divise un problème de grande taille en plusieurs (deux)

Sous-problèmes analogues, deux stratégies :

récursivité sur les données : on sépare les données en deux parties arbitraires, puis on résout les sous-problèmes, pour enfin combiner les résultats.
récursivité sur le résultat : on effectue un pré-traitement pour bien découper les données, puis à résoudre les sous-problèmes, pour que les sous-résultats se combinent d’eux-mêmes à la fin.

Récursivité sur les données :

On sépare les données en deux parties arbitraires, puis on résout les sous-problèmes, pour enfin combiner les résultats.
Comment obtenir un tableau trié, si l’on sait trier chaque moitié ?
Fusion de tableaux trié !
Fusion de deux tableaux triés

Algorithme (Fusion de tableaux triée)

Entrée : Tableaux T1, T2 triés de taille t1, t2,
Tableau T alloué de taille t = t1 + t2
Sortie : T avec les contenus T1 et T2 trié
i1 <- 0; i2 <- 0; i <- 0
tant que i1 < t1 et i2 < t2 faire
si T1[i1] < T2[i2] alors
T[i] <- T1[i1]; i++; i1++
sinon
T[i] <- T2[i2]; i++; i2++
si i1 < t1 alors
tant que i1 < t1 faire
T[i] <- T1[i1]; i++; i1++
sinon
tant que i2 < t2 faire
T[i] <- T2[i2]; i++; i2++
) Complexité : (t)

Tri par fusion (MergeSort)

Algorithme (TriFusion)
Entrée : Tableaux T de taille t, 0 min max < t Tableau Tmp alloué de taille t
Sortie : T trié.
si min <> max alors
mid <- (min+max) / 2
TriFusion(T, min, mid)
TriFusion(T, mid+1, max)
Fusion(T[min..mid], T[mid+1..max], Tmp)
Copie de Tmp dans T[min..max]
) Complexité : (t log(t))

Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2.
On note ck = dn le nombre de copies d’éléments si T est de taille n = 2k . On trouve
c0 = d1 = 0
c1 = d2 = 2 + 2 (fusion + copie)
c2 = d4 = 2c1 + 4 + 4 = 16 (rec + fusion + copie)
c3 = d8 = 2c2 + 8 + 8 = 48 (rec + fusion + copie)
c4 = d16 = 2c3 + 16 + 16 = 128 (rec + fusion + copie)
c5 = d32 = 2c4 + 32 + 32 = 320 (rec + fusion + copie)
c6 = d64 = 2c5 + 64 + 64 = 768 (rec + fusion + copie)
c7 = d128 = 2c6 + 128 + 128 = 1792 (rec + fusion + copie)

Proposition

Le nombre ck de copies d’éléments effectuées par le tri par fusion d’un tableau de n = 2k éléments vérifie :
c0 = 0 et ck = 2(ck 1 + 2k ) :
ck = 2k+1k = 2n log2(n) :
Preuve par récurrence :
vrai pour k = 0
si ck = 2k+1k alors
ck+1 = 2(ck + 2k+1) = 2(2k+1k + 2k+1) = 2k+2(k + 1)

Tri par fusion / insertion

Retenir (Tri mixte fusion / insertion)
Pour des petits tableaux le tri par insertion est plus rapide. Il vaut mieux l’utiliser comme cas de base de la récursion :
si max – min < SEUIL alors
InsertSort(T[min..max])
sinon
mid <- (min+max) / 2
TriFusion(T, min, mid)
TriFusion(T, mid+1, max)
Fusion(T[min..mid], T[mid+1..max], Tmp)
Copie de Tmp dans T
La valeur de SEUIL est déterminé expérimentalement.

Le tri par fusion n’est pas en place

On utilise un tableau de taille t supplémentaire (en fait en étant astucieux, un tableau de taille 2t suffit).
Définition
On dit qu’un tri est en place, s’il utilise un emplacement mémoire constant (O(1)) en plus du tableau pour stocker ses éléments.
Les tris par bulles et insertions sont en place ; Le tri par fusion n’est pas en place.
On aimerait bien avoir un trie en n log(n) en place. . .

Récursivité sur le résultat

On effectue un pré-traitement pour bien découper les données, puis
à résoudre les sous-problèmes, pour que les sous-résultats se combinent d’eux-mêmes à la fin.
Comment séparer les élements d’un tableau en deux pour que si l’on trie chaque partie le résultat soit triée ?
Partition d’un tableau !