Tri fusion

1. Algorithme de tri fusion
2. Exemple de tri fusion
3. Implémentation de l’algorithme de tri fusion
4. Complexité de l’algorithme de tri de fusion

Le tri fusion est l’un des algorithmes de tri les plus populaires et les plus efficaces. Il est basé sur le principe de l’algorithme diviser pour mieux régner. Il fonctionne en divisant le tableau en deux moitiés de manière répétée jusqu’à ce que nous obtenions un tableau divisé en éléments individuels. Un élément individuel est un tableau trié en soi. Le tri fusion fusionne de manière répétée ces petits tableaux triés pour produire de plus grands sous-réseaux triés jusqu’à ce que nous obtenions un tableau trié final. Il est largement utilisé dans les applications de commerce électronique.

Algorithme de tri fusion

La méthode de tri fusion descendante commence par le haut avec le tableau complet et se poursuit vers le bas avec des éléments individuels avec récursion.

Supposons que nous ayons un tableau non trié A[] contenant n éléments.

MergeSort()

Merge()

Exemple de tri fusion

Supposons que nous ayons le tableau : (5,3,4,2,1,6). Nous allons le trier en utilisant l’algorithme de tri fusion.

Nous obtenons le tableau trié - (1 2 3 4 5 6).

Implémentation de l’algorithme de tri fusion

#include <iostream>
using namespace std;

void merge(int arr[], int beg, int mid, int end) {
  int output[end - beg + 1];
  int i = beg, j = mid + 1, k = 0;
  // add smaller of both elements to the output
  while (i <= mid && j <= end) {
    if (arr[i] <= arr[j]) {
      output[k] = arr[i];
      k += 1;
      i += 1;
    } else {
      output[k] = arr[j];
      k += 1;
      j += 1;
    }
  }
  // remaining elements from first array
  while (i <= mid) {
    output[k] = arr[i];
    k += 1;
    i += 1;
  }
  // remaining elements from the second array
  while (j <= end) {
    output[k] = arr[j];
    k += 1;
    j += 1;
  }
  // copy output to the original array
  for (i = beg; i <= end; i += 1) {
    arr[i] = output[i - beg];
  }
}

void mergeSort(int arr[], int beg, int end) {
  if (beg < end) {
    int mid = (beg + end) / 2;
    // divide and conquer
    mergeSort(arr, beg, mid);      // divide : first half
    mergeSort(arr, mid + 1, end);  // divide: second half
    merge(arr, beg, mid, end);     // conquer
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  mergeSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri de fusion

Complexité temporelle

• Cas moyen

Le tri fusion est un algorithme récursif. La relation de récurrence suivante donne l’expression de la complexité temporelle pour tri fusion.

T(n) = 2T(n/2) + θ(n)

Le résultat de cette relation de récurrence donne T(n) = nLogn. Nous pouvons également le voir comme un tableau de taille n divisé en un maximum de parties logn, et la fusion de chaque partie prend O(n) de temps.

La complexité temporelle est donc de l’ordre de [Big Theta] : O(nLogn).

• Pire cas

La complexité temporelle la plus grave est [Big O] : O(nLogn).

• Meilleur cas

Le meilleur exemple de complexité temporelle est [Big Omega] : O(nLogn). C’est la même chose que la complexité temporelle dans le pire des cas.

Complexité spatiale

La complexité spatiale de l’algorithme de tri fusion est O(n) parce que n espace auxiliaire est nécessaire pour stocker le sous-réseau trié dans le tableau auxiliaire.