Chapitre 4

Diviser pour régner

1
 Gabarit général de l’approche diviser pour régner

„ Cette célèbre technique de conception a permis d’obtenir des

algorithmes très efficaces pour plusieurs problèmes différents
„ Décrivons le gabarit général utilisé pour ce type d’algorithme
„ Cette approche nécessite l’emploi d’un sous algorithme, que nous
nommerons adhoc, pour solutionner tout instance dont la taille est
suffisamment petite.
„ (plus petite qu’un seuil préalablement défini)

„ Désignons par |x| la taille de l’instance x

„ Le gabarit général est le suivant:

ALGORITHME DiviserPourRégner(x)
if |x| < seuil return adhoc(x)
diviser x en plus petites instances x1, x2, …, xr
for i ! 1 to r do yi"! DiviserPourRégner(xi)
recombiner les yi pour obtenir la solution y de x
return y

2
 Gabarit général de l’approche diviser pour régner (suite)

„ La valeur du seuil est une constante (préalablement choisie) qui ne

doit pas dépendre de la taille de l’instance
„ Sinon, ce ne serait plus un algorithme diviser pour régner
„ La taille de chaque petite instance xi devrait être la plus semblable
possible
„ Si une des petites instances est substantiellement plus grosse que
les autres, on ne divise plus et l’algorithme devient « diminuer pour
régner » (prochain chapitre).
„ Soit |x| = n (la taille de l’instance initiale)
„ L’algorithme divise x en r petites instances
„ Supposons que la taille de chaque petite instance est n/b
„ Souvent nous avons b = r (le cas le plus fréquent est b = r = 2).
„ Mais il arrive parfois que r ≠ b. Par exemple b = 2 et r = 3 ou b = 2
et r = 1 (voir exemple plus loin)

3
 La récurrence diviser pour régner

„ Supposons que f(n) est le temps requis pour diviser x en r petites

instances et recombiner les r solutions yi en une solution y pour x
„ Le temps d’exécution T(n) de l’algorithme est alors donné par la
récurrence diviser pour régner:

T(n) = r T(n/b) + f(n)

„ On suppose alors que chacune des r petites instances possède

exactement la même taille et ce pour tout appel récursif. Cela n’est
possible que lorsque n est une puissance de b: n = bk

„ Cependant, lorsque f(n) possède un ordre de croissance polynomial,

le théorème suivant nous informera que l’ordre de croissance de la
solution T(n) de cette récurrence sera donnée par une fonction
harmonieuse. Alors, en vertu de la règle de l’harmonie du chapitre 2,
nous pourrons en conclure que l’ordre de croissance obtenu pour T(n)
sera valide pour tout n (et non uniquement pour n = bk).

4
 Solution de la récurrence diviser pour régner

„ La solution (lorsque n #"$) de la récurrence diviser pour régner est

donnée par le théorème général:
„ Si T(n) obéit à la récurrence T(n) = r T(n/b) + f(n) pour n = bk (avec
k = 1, 2,…), et si f(n) % Θ(nd) avec d & 0, alors:

„ Si la récurrence est donnée par l’inégalité T(n) ≤ r T(n/b) + f(n),

alors ce théorème s’applique en remplaçant Θ() par O()
„ Si la récurrence est donnée par l’inégalité T(n) & r T(n/b) + f(n),
alors ce théorème s’applique en remplaçant Θ() par Ω()

5
 Observations sur la solution de la récurrence

„ Seul le comportement asymptotique (n # $) est spécifié.

„ Cette solution asymptotique ne dépend pas de la valeur du seuil.
„ La valeur du seuil d’un algorithme diviser pour régner n’affecte donc
pas l’ordre de croissance de son temps d’exécution.
„ L’ordre de croissance de T(n) dépend uniquement de d lorsque r ≤ bd.
„ Si r > bd, c’est r et b qui affectent l’ordre de croissance de T(n).
„ Pour utiliser le théorème général, il suffit de vérifier que T(n) obéi à la
récurrence diviser pour régner pour n = bk (seulement)
„ Nous obtenons une borne asymptotique exacte pour T(n) lorsque
T(n) = r T(n/b) + f(n). Cette borne dépend de Θ(f(n)).
„ Nous obtenons une borne asymptotique supérieure pour T(n) lorsque
T(n) ≤ r T(n/b) + f(n). Cette borne dépend de O(f(n)).
„ Nous obtenons une borne asymptotique inférieure pour T(n) lorsque
T(n) & r T(n/b) + f(n). Cette borne dépend de Ω(f(n)).

6
 Le tri fusion

„ C’est un exemple classique d’algorithme diviser pour régner

„ Pour trier A[0..n-1]:
„ On divise d’abord A en deux moitiés A[0.. ⎣n/2⎦-1] et A[⎣n/2⎦.. n-1]
„ On tri récursivement chacune de ces deux moitiés
„ On fusionne ces deux moitiés triées en un seul tableau trié
„ Le seuil est fixé à n = 1 (un tableau avec un seul élément est
toujours trié; il n’y a donc rien à faire dans ce cas)

ALGORITHME MergeSort(A[0..n-1])
//Entrée: le tableau A
//Sortie: le tableau A trié
if n > 1
copy A[0.. ⎣n/2⎦-1] to B[0.. ⎣n/2⎦-1]
copy A[⎣n/2⎦.. n-1] to C[0.. ⎡n/2⎤-1]
MergeSort(B[0.. ⎣n/2⎦-1])
MergeSort(C[0.. ⎡n/2⎤-1])
Merge(B, C, A)
(Delete B; Delete C)
7
 La procédure de fusion

„ Deux indexes pointent initialement sur le premier élément de chaque tableau

„ Le plus petit de ces deux éléments pointés est copié à la première place de
disponible dans le nouveau tableau
„ L’index du plus petit élément est incrémenté de 1
„ Nous continuons jusqu’à ce que tous les éléments d’un des tableaux ont été
copiés et, ensuite, nous copions (dans l’ordre) tous les éléments restants de
l’autre tableau

ALGORITHME Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])

I ! 0; j ! 0; k ! 0
while i < p and j < q do
if B[i] ≤ C[j] then A[k] ! B[i]; i ! i + 1
else A[k] ! C[j]; j ! j + 1
k!k+1
if i = p then copy C[j..q-1] to A[k..p+q-1]
else copy B[i..p-1] to A[k..p+q-1]

8
Exemple illustrant l’algorithme du tri fusion

9
 Analyse de l’algorithme du tri fusion

„ Peu importe notre choix pour l’opération de base, le nombre

d’opérations de base C(n) effectuées par MergeSort(A[0..n-1]) sera,
dans le pire cas et le meilleur cas, donné par:
„ C(n) = 2 C(n/2) + Cmerge(n) + Cb-c(n) lorsque n = 2k
„ où Cmerge(n) est le nombre d’opérations de base effectuées par
Merge(B[0..(n/2)-1], C[0..(n/2)-1], A[0..n-1])
„ et Cb-c(n) est le temps requis pour construire les tableaux
additionnels B et C et les détruires
„ Il s’agit donc d’une récurrence diviser pour régner avec r = b = 2
„ Pour appliquer le théorème général sur C(n), nous devons déterminer
l’ordre de croissance de Cmerge(n) et de Cb-c(n).
„ Pour Cb-c(n), nous pouvons choisir l’affectation (le copiage d’un
élément à l’autre) comme opération de base.
„ Puisqu’il y a n affectations, on a Cb-c(n) = n.

10
 Analyse de l’algorithme du tri fusion (suite)

„ Pour Cmerge(n), notez que Merge() est constitué de deux parties

distinctes:
„ Dans la première partie, il y a des comparaisons B[i] ≤ C[j] et des
affectations d’un élément d’un tableau vers un élément d’un autre
tableau. Chaque comparaison est toujours accompagnée d’une
affectation.
„ Dans la seconde partie, il y a seulement des affectations car l’on
copie les éléments non copiés (lors de l’exécution de la 1ière
partie) d’un tableau vers le tableau final.
„ Nous pouvons donc choisir l’affectation comme opération de base
dans Merge().
„ Dans tous les cas (meilleurs et pires), il y a toujours n éléments copiés
(ou affectés) d’un tableau vers un autre lorsque le tableau final A
possède n éléments.
„ Le nombre d’affectations effectuées par Merge(B,C,A) est donc
toujours égal à n lorsque le tableau final A possède n éléments.
„ Alors Cmerge(n) = n.

11
 Analyse de l’algorithme du tri fusion (suite)

„ La relation de récurrence pour C(n) est alors donnée par

„ C(n) = 2 C(n/2) + f(n) avec f(n) % Θ(n) (lorsque n = 2k)
„ C’est une récurrence diviser pour régner avec r = b = 2 et f(n)%Θ(n).
Donc d = 1 et r = bd. Le théorème général nous donne alors:

C(n) % Θ(n log n)

„ C’est donc mieux que le Θ(n2) de l’algorithme force brute SelectSort()

„ Il est possible de démontrer que tout algorithme de tri par comparaison
doit nécessairement avoir Cworst(n) % Ω(n log n)
„ Le tri fusion est donc asymptotiquement optimal en pire cas!
„ Cependant, le tri fusion ne tri pas sur place. Il nécessite le stockage de
Θ(n) éléments additionnels pour les tableaux B et C lorsque l’on détruit
B et C après chaque utilisation. (Si l’on ne détruit jamais B et C, ce
sera Θ(n log n): pourquoi?)

12
 Le tri rapide

„ Le tri rapide est peut-être l’algorithme de tri le plus fréquemment utilisé

„ C’est également un algorithme diviser pour régner
„ La première étape de l’algorithme est de partitionner un tableau
A[0..n-1] autour d’un élément A[s] appelé le pivot.
„ Le tableau A[0..n-1] est partitionné autour du pivot A[s] ssi les
éléments A[0] jusqu’à A[s-1] sont tous ≤ A[s] et les éléments A[s+1]
jusqu’à A[n-1] sont tous & A[s].
„ Lorsque cette partition est effectuée, l’élément A[s] occupe sa
position finale dans le tableau trié.
„ Pour trier le tableau, il suffit alors de répéter (récursivement) cette
procédure pour le sous tableau A[0..s-1] et le sous tableau A[s+1..n-1]
„ Pour chaque appel, on partitionne le sous tableau autour d’un
élément pivot choisi dans le sous tableau

13
 Le tri rapide (suite)

ALGORITHME QuickSort(A[l..r])
//Entrée: le sous tableau A[l..r] de A[0..n-1]
//Sortie: le sous tableau A[l..r] trié
if l < r
s ! Partition(A[l..r])
QuickSort(A[l..s-1])
QuickSort(A[s+1..r])

„ La procédure Partition(A[l..r]) retourne la position s du pivot A[s] autour duquel

A[l..r] est partitionné
„ Le pivot choisi par Partition(A[l..r]) est le premier élément A[l] = p, ensuite

le tableau A[l..r] est partitionné autour de cet élément p

„ Deux balayages sont utilisés pour partitionner A[l..r] autour de p:
„ Le balayage vers la droite: on examine séquentiellement tous les éléments

à partir de A[l+1] et l’on s’arrête au 1er élément A[i] tel que A[i] & p
„ Le balayage vers la gauche: on examine séquentiellement tous les

éléments à partir de A[r] et l’on s’arrête au 1er élément A[j] tel que A[j] ≤ p

14
 Le tri rapide (suite)

„ Lorsque ces deux balayages s’arrêtent: nous avons l’une des trois
possibilités suivantes: i < j, i > j ou i = j.
„ Lorsque i < j: on interchange A[i] et A[j] et continuons les deux balayages:
#i !j
p tous · p &p ·p tous & p

„ Lorsque i > j: on interchange p avec A[j] et A[l..r] est alors partitionné!

!j #i
p tous · p ·p &p tous & p

„ Lorsque i = j: on a alors A[i] = A[j] = p et A[l..r] est alors partitionné!

#i=j!
p tous · p =p tous & p

„ Combinaisons des 2 derniers cas: on interchange p avec A[j] lorsque i & j

15
Le procédure Partition(A[l..r])

16
 Le procédure Partition(A[l..r])

„ Remarque: dans le pseudo code précédent, l’index i déborde et acquière une

valeur > r lorsque A[l] > A[k] ' k % {l+1..r}
„ Pour éviter cela il suffit d’ajouter une sentinelle, i.e. un élément A[n] tel que
A[n] & A[0] (et de ne trier que le tableau A[0..n-1])
„ Dans ce cas, Partition(A[0..n-1]) retournera s = n-1(comme il se doit)

lorsque A[0] > A[k] ' k % {1..n-1} et l’index i arrêtera en position n.

„ De plus, lors des invocations futures de Partition(A[l..r]), les éléments de

A[l..r] seront tous ≤ A[r+1]. Alors l’élément A[r+1] agira comme sentinelle
et empêchera l’index i d’aller au delà de r+1

„ Une autre façon d’éviter ce problème est de choisir, comme pivot, l’élément
médian entre les trois éléments suivants: A[l], A[r] et A[⎣(l+r)/2⎦]

„ L’idée de partition est également utilisée pour le problème de trouver le kième

plus petit élément d’un tableau (voir prochain chapitre)

17
Exemple d’exécution du tri rapide

18
 Analyse du tri rapide

„ Utilisons la comparaison entre 2 éléments pour l’opération de base.

„ Le nombre de comparaisons effectuées par Partition(A[0..n-1]) est de
n+1 lorsque les indices i et j se croisent et de n lorsqu’ils coïncident.
„ Dans tous les cas, le nombre de comparaisons sera % Θ(n).
„ Alors Cpartition(n) % Θ(n)

„ Les meilleurs cas pour le tri rapide sont ceux pour lesquels le pivot est
toujours l’élément médian. Donc, pour n = 2k, nous avons:
„ Cbest(n) = 2Cbest(n/2) + Cpartition(n)
„ Alors: Cbest(n) % Θ(n log n) selon le théorème général (b=r=2, d=1)

„ Les pires cas sont, entre autre, ceux pour lesquels le pivot est toujours
le plus petit élément du sous tableau.
„ Cela se produit lorsque A[0..n-1] est déjà trié en ordre croissant.
„ Dans ces pires cas, Quicksort fait un appel récursif sur un tableau
vide et un autre sur A[1..n-1]. Nous avons alors:
„ Cworst(n) = Cworst(n-1) + Cpartition(n)

19
 Analyse du tri rapide (suite)

„ La méthode des substitutions à rebours donne:

„ Cworst(n) = Cworst(n-1) + Cpartition(n)
= Cworst(n-2) + Cpartition(n-1) + Cpartition(n)
…
= Cworst(n-i) + Cpartition(n-i+1) … + Cpartition(n)
= Cworst(1) + Cpartition(2) … + Cpartition(n) (pour i = n-1)

„ Puisque Cworst(1) = 0 et que Cpartition(i) = i + 1 en pire cas. Nous avons:

„ Conclusion: le temps d’exécution du tri rapide est Θ(n2) en pire cas et

Θ(n log n) en meilleur cas.

20
 Analyse du cas moyen du tri rapide

„ Quel est alors son temps d’exécution en moyenne?

„ Supposons, pour simplifier l’analyse, que tous les éléments à trier sont
distincts et que toutes les n! configurations possibles des éléments
dans A[0..n-1] sont équiprobables.
„ Dans ces circonstances, la partition du tableau A[0..n-1] peut survenir
à chaque position s % {0..n-1} avec une même probabilité de 1/n.
„ Le temps d’exécution moyen sera alors donné par:

21
Analyse du cas moyen du tri rapide (suite)

22
Analyse du cas moyen du tri rapide (suite)

23
Analyse du cas moyen du tri rapide (suite)

24
 Analyse du cas moyen du tri rapide (suite)

„ Puisque B(n) = Cavg(n)/(n+1), nous obtenons finalement:

„ Pour les grandes valeurs de n, on a : Cavg(n) ( 2n ln(n) ( 1.38 n lg(n)

„ La faible valeur de cette constante (1.38) donne un temps d’exécution

moyen inférieur au tri par tas (voir + loin) ayant Cworst(n) % Θ(n log n)

„ Le tri fusion donne Cavg(n) ( n lg(n) mais, contrairement au tri rapide,

il ne tri pas sur place.

„ L’excellente efficacité en moyenne du tri rapide en fait un candidat de

choix lorsque le tableau à trier n’est pas déjà quasiment trié

25
 Recherche binaire dans un tableau trié

„ Le problème est de déterminer si un élément K se trouve dans un

tableau trié A[0..n-1]. S’il s’y trouve, on doit obtenir l’index de la
position de cet élément.
„ L’idée de la recherche binaire est de comparer K à l’élément A[m] situé
au milieu du tableau.
„ Si K = A[m] alors on retourne m
„ Si K < A[m] alors on cherche K parmi A[0..m-1]
„ Si K > A[m] alors on cherche K parmi A[m+1..n-1]

ALGORITHM BinarySearch(A[0..n-1])
L ! 0; r ! n-1
while l ≤ r do
m ! ⎣(l + r)/2⎦
if K = A[m] then return m
else if K < A[m] then r ! m - 1
else l ! m + 1
return -1
26
 Analyse de la recherche binaire

„ Choisissons le prédicat K = A[m] pour l’opération de base

„ Cbest(n) = 1 car, dans les meilleurs cas, K = A[⎣(n-1)/2⎦]

„ Pour l’analyse des pires cas, supposons que n = 2k car, pour ces cas,
nous divisons la taille du tableau exactement par 2 après l’exécution
d’une opération de base.
„ Ainsi, pour n = 2k, nous avons:
„ Cworst(n) = Cworst(n/2) + 1

„ Alors, le théorème général nous dit que pour r = 1, b = 2 et d = 0, nous

avons:
„ Cworst(n) % Θ(log(n))

„ C’est donc extrêmement rapide!

27
 Analyse de la recherche binaire (suite)

„ Pour connaître exactement le nombre de fois que l’opération de base

est effectuée, nous pouvons utiliser la méthode des substitutions à
rebours pour n = 2k. Cela donne:
„ Cworst(2k) = C(2k-1) + 1 = C(2k-2) + 2 … = C(2k-i) + i = C(1) + k
„ Or C(1) = 1. Alors: Cworst(n) = k + 1 = lg(n) + 1 (lorsque n = 2k)

„ Mais ce n’est pas un algorithme diviser pour régner car, à chaque

itération, on divise l’instance en deux parties mais on ignore une des
parties (pour travailler sur l’autre).
„ C’est donc un algorithme diminuer pour régner (prochain chapitre).

28