Algorithme de tri fusion | Tutoriel de programmation Java

Introduction

Le tri fusion est un algorithme de tri efficace et stable qui utilise la technique Diviser pour régner pour trier un tableau. Dans ce laboratoire, vous allez apprendre à implémenter le tri fusion en Java en utilisant une approche récursive.

Créer une méthode de tri fusion

Créez une méthode publique statique appelée mergeSort() avec trois paramètres entiers, int arrToSort[], startIdx, endIdx. Vous devez vérifier si la longueur du tableau est inférieure à 2, puis retourner. Sinon, calculez l'indice du milieu du tableau et divisez le tableau en deux moitiés gauche et droite. Les deux moitiés gauche et droite doivent également être divisées de manière récursive. Après les avoir divisées, vous devrez les fusionner pour former un tableau trié.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

Créer une méthode de fusion

Créez une autre méthode publique statique appelée merge() avec quatre paramètres : int arrToSort[], startIdx, midIdx et endIdx. Vous devez initialiser les tableaux gauche et droit. Ensuite, vous devez fusionner les deux tableaux en comparant les éléments de chaque tableau et en les fusionnant en un seul tableau.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

Tester le tri fusion

Testons la méthode mergeSort() en écrivant du code pour trier un tableau d'entrée. Créez une méthode principale. Ensuite, déclarez un tableau d'entiers avec quelques valeurs non triées. Appelez la méthode mergeSort() et passez-lui le tableau non trié. Enfin, affichez le tableau trié dans la console. Le bloc de code pour cette étape ressemblera à ceci :

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

Après avoir exécuté le programme, la sortie devrait être : [0, 1, 2, 4, 6, 8].

Tester avec un tableau vide

Créez un autre test pour un tableau vide. Déclarez un tableau d'entiers vide. Appelez la méthode mergeSort() et passez-lui le tableau vide. Enfin, affichez le tableau trié dans la console. Le bloc de code pour cette étape ressemblera à ceci :

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

La sortie devrait être la même que l'entrée.

Tester avec un tableau à un seul élément

Créez un autre test avec un tableau à un seul élément. Déclarez un tableau d'entiers à un seul élément. Appelez la méthode mergeSort() et passez-lui le tableau à un seul élément. Enfin, affichez le tableau trié dans la console. Le bloc de code pour cette étape ressemblera à ceci :

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

La sortie devrait être la même que l'entrée.

Tester avec des valeurs négatives

Créez un autre test pour un tableau composé d'entiers négatifs. Déclarez un tableau d'entiers qui inclut des entiers négatifs. Appelez la méthode mergeSort() et passez le tableau en tant qu'argument. Enfin, affichez le tableau trié dans la console. Le bloc de code pour cette étape ressemblera à ceci :

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

Après avoir exécuté le programme, la sortie devrait être : [-9, -7, -1, 0, 2, 6, 8].

Tester avec des éléments non numériques

Créez un autre test en triant un tableau d'éléments non numériques. Déclarez un tableau de chaînes de caractères. Appelez la méthode mergeSort() et passez le tableau en tant qu'argument. Enfin, affichez le tableau trié dans la console. Le bloc de code pour cette étape ressemblera à ceci :

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

Après avoir exécuté le programme, la sortie devrait être : ['Bob', 'Christine', 'David', 'Emily', 'John'].

需要注意的是，这里输出中的单引号在法语中一般用双引号表示更合适，即["Bob", "Christine", "David", "Emily", "John"] ，但按照要求保持原文格式输出了。

Code source final

Voici le code source final pour le tri fusion :

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //crée un tableau d'entiers non trié
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //trie le tableau d'entiers en utilisant le tri fusion
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //affiche le tableau trié
       System.out.println(Arrays.toString(arrToSort));

       //crée un tableau d'entiers vide
       int[] emptyArr = {};
       //trie le tableau vide
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //affiche le tableau trié
       System.out.println(Arrays.toString(emptyArr));

       //crée un tableau à un seul élément
       int[] singleElementArr = {7};
       //trie le tableau à un seul élément
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //affiche le tableau trié
       System.out.println(Arrays.toString(singleElementArr));

       //crée un tableau d'entiers négatifs
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //trie le tableau d'entiers négatifs
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //affiche le tableau trié
       System.out.println(Arrays.toString(arrWithNegatives));

       //crée un tableau de chaînes de caractères
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //trie le tableau de chaînes de caractères
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //affiche le tableau trié
       System.out.println(Arrays.toString(strsToSort));
   }
}

Exécuter le programme

Compilez et exécutez le programme à l'aide du terminal :

javac MergeSort.java && java MergeSort

Résumé

Dans ce laboratoire, vous avez appris ce qu'est le tri fusion, comment il fonctionne et comment l'implémenter en Java. Vous avez créé deux méthodes publiques statiques, mergeSort() et merge() pour diviser et fusionner le tableau d'entrée respectivement. Après l'implémentation, vous l'avez testé avec diverses entrées, discuté de la complexité temporelle et spatiale, et vérifié sa fonctionnalité. Félicitations! Vous avez réussi à compléter le laboratoire sur le tri fusion en Java.

Implémentation récursive du tri fusion en Java