Fusionner le tri en Java

1. Introduction

Dans ce didacticiel, nous examinerons l'algorithme Merge Sort et son implémentation en Java .

Le tri par fusion est l'une des techniques de tri les plus efficaces et il est basé sur le paradigme «diviser et conquérir».

2. L'algorithme

Le tri par fusion est un algorithme «diviser et conquérir» dans lequel nous divisons d'abord le problème en sous-problèmes. Lorsque les solutions pour les sous-problèmes sont prêtes, nous les combinons pour obtenir la solution finale au problème.

C'est l'un des algorithmes qui peuvent être facilement implémentés en utilisant la récursivité car nous traitons les sous-problèmes plutôt que le problème principal.

L'algorithme peut être décrit comme le processus en 2 étapes suivant:

  • Divide: dans cette étape, nous divisons le tableau d'entrée en 2 moitiés , le pivot étant le milieu du tableau. Cette étape est effectuée de manière récursive pour tous les demi-tableaux jusqu'à ce qu'il n'y ait plus de demi-tableaux à diviser.
  • Conquérir: dans cette étape, nous trions et fusionnons les tableaux divisés de bas en haut et obtenons le tableau trié.

Le diagramme suivant montre le processus de tri de fusion complet pour un exemple de tableau {10, 6, 8, 5, 7, 3, 4}.

Si nous regardons de plus près le diagramme, nous pouvons voir que le tableau est divisé récursivement en deux moitiés jusqu'à ce que la taille devienne 1. Une fois que la taille devient 1, les processus de fusion entrent en action et commencent à fusionner les tableaux pendant le tri:

3. Mise en œuvre

Pour l'implémentation, nous allons écrire une fonction mergeSort qui prend le tableau d'entrée et sa longueur comme paramètres. Ce sera une fonction récursive donc nous avons besoin de la base et des conditions récursives.

La condition de base vérifie si la longueur du tableau est de 1 et elle retournera simplement. Pour le reste des cas, l'appel récursif sera exécuté.

Pour le cas récursif, nous obtenons l'index du milieu et créons deux tableaux temporaires l [] et r [] . La fonction mergeSort est ensuite appelée récursivement pour les deux sous-tableaux:

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

Nous appelons ensuite la fonction de fusion qui prend en entrée et à la fois les sous-tableaux et les indices de début et de fin des deux sous-tableaux .

La fonction de fusion compare les éléments des deux sous-tableaux un par un et place le plus petit élément dans le tableau d'entrée.

Lorsque nous atteignons la fin de l'un des sous-tableaux, le reste des éléments de l'autre tableau est copié dans le tableau d'entrée, nous donnant ainsi le tableau trié final:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Le test unitaire du programme:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Complexité

Comme le tri par fusion est un algorithme récursif, la complexité temporelle peut être exprimée comme la relation récursive suivante:

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

2T (n / 2) correspond au temps requis pour trier les sous-tableaux et O (n) temps pour fusionner le tableau entier.

Une fois résolue, la complexité temporelle viendra à O (nLogn).

Cela est vrai pour le pire, la moyenne et le meilleur des cas, car il divisera toujours le tableau en deux puis fusionnera.

La complexité spatiale de l'algorithme est O (n) car nous créons des tableaux temporaires dans chaque appel récursif.

5. Conclusion

Dans ce rapide tutoriel, nous avons vu le fonctionnement de l'algorithme de tri par fusion et comment nous pouvons l'implémenter en Java.

L'ensemble du code de travail est disponible à l'adresse over sur GitHub.