DAA - Tri de fusion

Dans ce chapitre, nous aborderons le tri par fusion et analyserons sa complexité.

Énoncé du problème

Le problème du tri d'une liste de nombres se prête immédiatement à une stratégie de division-pour-conquérir: diviser la liste en deux moitiés, trier récursivement chaque moitié, puis fusionner les deux sous-listes triées.

Solution

Dans cet algorithme, les nombres sont stockés dans un tableau numbers[]. Ici,p et q représente l'index de début et de fin d'un sous-tableau.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

Une analyse

Considérons, le temps d'exécution de Merge-Sort comme T(n). Par conséquent,

$ T (n) = \ begin {cases} c & if \: n \ leqslant 1 \\ 2 \: x \: T (\ frac {n} {2}) + d \: x \: n & sinon \ end {cases} $ où c et d sont des constantes

Par conséquent, en utilisant cette relation de récurrence,

$$ T (n) = 2 ^ i T (\ frac {n} {2 ^ i}) + idn $$

Comme, $ i = log \: n, \: T (n) = 2 ^ {log \: n} T (\ frac {n} {2 ^ {log \: n}}) + log \: ndn $

$ = \: cn + dnlog \: n $

Par conséquent, $ T (n) = O (n \: log \: n) $

Exemple

Dans l'exemple suivant, nous avons montré pas à pas l'algorithme Merge-Sort. Tout d'abord, chaque tableau d'itération est divisé en deux sous-tableaux, jusqu'à ce que le sous-tableau ne contienne qu'un seul élément. Lorsque ces sous-tableaux ne peuvent plus être divisés, des opérations de fusion sont effectuées.