Comment fusionner deux tableaux triés en Java

1. Introduction

Dans ce didacticiel, nous allons apprendre à fusionner deux tableaux triés en un seul tableau trié.

2. Problème

Comprenons le problème. Nous avons deux tableaux triés et nous aimerions les fusionner en un seul.

3. Algorithme

Lorsque nous analysons le problème, il est assez facile d'observer que nous pouvons résoudre ce problème en utilisant l'opération de fusion de Merge Sort.

Disons que nous avons deux tableaux triés foo et bar de longueur fooLength et barLength , respectivement. Ensuite, nous pouvons déclarer un autre tableau fusionné de taille fooLength + barLength .

Nous devrions alors parcourir les deux tableaux dans la même boucle. Nous maintiendrons une valeur d'index actuelle pour chaque, fooPosition et barPosition . Sur une itération donnée de notre boucle, nous prenons le tableau qui a l'élément de plus petite valeur à leur index et faisons avancer cet index. Cet élément occupera la position suivante dans le tableau fusionné .

Enfin, une fois que nous avons transféré tous les éléments d'un tableau, nous copierons le reste de l'autre dans le tableau fusionné .

Voyons maintenant le processus en images pour mieux comprendre l'algorithme.

Étape 1:

Nous commençons par comparer les éléments des deux tableaux et nous choisissons le plus petit.

Ensuite, nous incrémentons la position dans le premier tableau.

Étape 2:

Ici, nous incrémentons la position dans le deuxième tableau et passons à l'élément suivant qui est 8.

Étape 3:

À la fin de cette itération, nous avons parcouru tous les éléments du premier tableau.

Étape 4:

Dans cette étape, nous copions simplement tous les éléments restants du deuxième tableau vers le résultat .

4. Mise en œuvre

Voyons maintenant comment l'implémenter:

public static int[] merge(int[] foo, int[] bar) { int fooLength = foo.length; int barLength = bar.length; int[] merged = new int[fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo[fooPosition] < bar[barPosition]) { merged[mergedPosition++] = foo[fooPosition++]; } else { merged[mergedPosition++] = bar[barPosition++]; } } while (fooPosition < fooLength) { merged[mergedPosition++] = foo[fooPosition++]; } while (barPosition < barLength) { merged[mergedPosition++] = bar[barPosition++]; } return merged; }

Et procédons avec un bref test:

@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int[] foo = { 3, 7 }; int[] bar = { 4, 8, 11 }; int[] merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar)); }

5. Complexité

Nous parcourons les deux tableaux et choisissons le plus petit élément. En fin de compte, nous copions le reste des éléments du foo ou du tableau de barres . Ainsi, la complexité temporelle devient O (fooLength + barLength) . Nous avons utilisé un tableau auxiliaire pour obtenir le résultat. La complexité de l'espace est donc également O (fooLength + barLength) .

6. Conclusion

Dans ce didacticiel, nous avons appris à fusionner deux tableaux triés en un seul.

Comme d'habitude, le code source de ce tutoriel se trouve à l'adresse over sur GitHub.