5. Tri fusion

5.1. Spécification

On sépare le tableau en deux sous-tableaux de même taille, que l'on trie récursivement ; ensuite, on fusionne les deux sous-tableaux en gardant l'ordre (application du principe de diviser pour régner). Le cas de base correspond au tri d'un seul élément, qui ne nécessite aucune opération.

Pour la fusion des tableaux, on prend trois paramètres tels que p≤q<rp≤q<r, en sachant que les deux sous-tableaux à fusionner (A[p..q] et A[q+1..r]) sont déjà triés.

5.2. Algorithme

Tri par fusion : MergeSort(A, p, r)

Si p < r Alors

                    q <- round down (p+r)/2

                    MergeSort(A, p, q)

                    MergeSort(A, q + 1, r)

                    Merge(A, p, q, r)

Fusion de tableaux : Merge(A, p, q, r)

L[1..n1 + 1], R[1..n2 + 1] deux tableaux

n1 <- q - p + 1

n2 <- r – q

 

pour i <- 1 jusqu’à n1 faire

                    L[i] <- A[p + i - 1]

pour j ß 1 jusqu’à n2 faire

                    R[j] <- A[q + j]

 

L[n1 + 1] <- 1

R[n2 + 1] <- 1

 

i <- 1

j <- 1

pour k <- p jusqu’à r faire

                    Si L[i] <= R[j] Alors

                                         A[k] <- L[i]

                                         i <- i + 1

                    Sinon

                                         A[k] <- R[j]

                                         j <- j + 1

Last modified: Sunday, 7 February 2021, 11:12 AM