Comprendre l'algorithme de tri par fusion (avec des exemples en Java)

Tri par fusion : un guide complet

Merge Sort est un algorithme de tri très efficace fréquemment utilisé dans divers langages de programmation, soit indépendamment, soit dans le cadre d'une approche hybride. Son fondement réside dans le paradigme Diviser pour Régner : un problème est divisé en sous-problèmes plus petits, résolus individuellement, et leurs solutions combinées pour le résultat final. Merge Sort divise de manière récursive la liste d'entrée en moitiés, trie chaque moitié, puis fusionne les moitiés triées pour produire une liste entièrement triée.

Comprendre le processus de tri par fusion

Illustrons le processus de tri par fusion à l'aide d'un exemple de tableau :

Cette image représente la division récursive du tableau.

Cette image montre la fusion de sous-tableaux triés.

Implémentation du tri par fusion

Vous trouverez ci-dessous une implémentation Java de l'algorithme Merge Sort :

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

Explication du code

La méthode mergeSort divise le tableau de manière récursive jusqu'à ce que les sous-tableaux ne contiennent qu'un seul élément. La méthode merge est cruciale ; il prend les sous-tableaux triés et les fusionne efficacement en un seul tableau trié. Le processus de fusion implique de comparer les éléments des deux sous-tableaux et de placer le plus petit élément dans le tableau principal.

Cette image illustre l'étape de fusion.

La sortie du code est :

Tableau non trié : [8, 2, 6, 4, 9, 1] Tableau trié : [1, 2, 4, 6, 8, 9]

Complexité algorithmique

• Complexité temporelle : O(n log n) dans tous les cas (meilleur, moyen et pire). En effet, l'approche diviser pour régner reste cohérente quel que soit l'ordre initial du tableau d'entrée.
• Complexité spatiale : O(n) en raison de l'espace supplémentaire requis pour les tableaux temporaires lors de l'opération de fusion.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!