Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_programmes_a_connaitre:algorithmique_term:diviser_pour_regner_algo [2021/01/26 10:39]
rd
+++ les_programmes_a_connaitre:algorithmique_term:diviser_pour_regner_algo [2021/01/26 11:02]
rd
@@ Ligne 3: / Ligne 3: @@
-Cette méthode algorithmique permet de résoudre un problème. Tout d'abord, on divise ce problème en une multitude de petits problèmes, puis ces sous-problèmes étant plus simples, sont ensuite résolus, et on recombine enfin les petits problèmes résolus afin d'obtenir la solution du problème de départ. (je vous invite à voir la [[les_fiches_revisions:langages_programmation:recursivite|récursivité]] sur laquelle cette méthode est souvent basée)
+Cette méthode algorithmique permet de résoudre un problème. Tout d'abord, on divise ce problème en une multitude de petits problèmes, puis ces sous problèmes étant plus simples, sont ensuite résolus, et on recombine enfin les petits problèmes résolus afin d'obtenir la solution du problème de départ. (je vous invite à voir la [[les_fiches_revisions:langages_programmation:recursivite|récursivité]] sur laquelle cette méthode est souvent basée)
 Comme son nom l'indique (ou pas), ce paradigme est séparée en trois étapes.
@@ Ligne 10: / Ligne 10: @@
   * **__COMBINER :__** assemble les solutions des sous-problèmes afin d'avoir la solution du problème initial
+\\
+L'algorithme de __tri-fusion__ est un algorithme de tri utilisant la méthode "diviser pour régner" et utilisant aussi la récursivité. Ainsi il est plus rapide et efficace ayant un complexité de "O(n.log(n))" :
+<code>
+VARIABLE
+A : tableau d'entiers
+L : tableau d'entiers
+R : tableau d'entiers
+p : entier
+q : entier
+r : entier
+n1 : entier
+n2 : entier
+DEBUT
+FUSION (A, p, q, r):
+  n1 ← q - p + 1
+  n2 ← r - q
+  créer tableau L[1..n1+1] et R[1..n2+1]
+  pour i ← 1 à n1:
+    L[i] ← A[p+i-1]
+  fin pour
+  pour j ← 1 à n2:
+    R[j] ← A[q+j]
+  fin pour
+  L[n1+1] ← ∞
+  R[n2+1] ← ∞
+  i ← 1
+  j ← 1
+  pour k ← p à r:
+    si L[i] ⩽ R[j]:
+      A[k] ← L[i]
+      i ← i + 1
+    sinon:
+      A[k] ← R[j]
+      j ← j + 1
+    fin si
+  fin pour
+fin FUSION
+TRI-FUSION(A, p, r):
+  si p < r:
+    q = (p + r) / 2
+    TRI-FUSION(A, p, q)
+    TRI-FUSION(A, q+1, r)
+    FUSION(A, p, q, r)
+  fin si
+fin TRI-FUSION
+FIN
+</code>

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page