Comment trier un tableau en Java

Le tri est l’une des opérations les plus courantes et les plus nécessaires en programmation. Il représente l’ordre d’un ensemble d’éléments dans un ordre spécifique. Cet article concerne les méthodes standard de tri des tableaux en Java.

En bref sur le tri

Le tri est donc le classement d’un ensemble de données. Dans notre cas, des tableaux. Le but du tri des tableaux ou d’autres structures de données est de faciliter la recherche, la manipulation ou l’analyse des données de la collection. Les programmeurs ont si souvent besoin de trier que tout langage de programmation inclut des méthodes intégrées pour trier les tableaux, les listes et autres structures de données ordonnées. Pour utiliser de telles méthodes, appelez-les. L'opération est simplifiée au maximum. Habituellement, les méthodes intégrées sont optimisées au maximum ; dans la plupart des cas, les utiliser pour votre travail ou vos projets est une bonne idée. Cependant, presque tous les programmeurs, au cours de leurs études, doivent implémenter eux-mêmes des algorithmes de tri. Ces exercices parfaits vous apprennent donc à comprendre l’essence même de la programmation. De plus, vous avez parfois besoin de méthodes de tri non standard dans le travail. Il existe de nombreux algorithmes de tri. Ils présentent des forces et des faiblesses selon le type ou la taille des ensembles de données. Les algorithmes de tri standard incluent le tri à bulles, le tri par sélection, le tri par insertion, le tri par fusion et le tri rapide.

Méthode intégrée pour trier les tableaux en Java : Arrays.sort

Commençons par le plus simple. Quelqu'un a déjà écrit pour nous une méthode de tri des tableaux en Java. Cette méthode appartient à la classe Arrays , plus précisément java.util.Arrays . Cette classe contient diverses méthodes pour travailler avec des tableaux, telles que le tri et la recherche. La méthode Arrays.sort fournit un moyen pratique de trier les tableaux en Java, qu'ils contiennent des chaînes, des entiers ou d'autres éléments. Il existe plusieurs variantes de la méthode Arrays.sort en Java. Voici quelques méthodes de tri couramment utilisées dans la classe Arrays :

• Arrays.sort(Array) : utilisez-le pour trier des tableaux de types primitifs ou d'objets par ordre croissant. Il utilise l’ordre naturel des éléments.
• Arrays.sort(Array, fromIndex, toIndex) : Cette méthode de tri surchargée vous permet de trier uniquement une partie du tableau spécifié par les paramètres fromIndex et toIndex.
• Arrays.sort(Array, comparator) : celui-ci sert à trier des tableaux d'objets à l'aide d'un comparateur personnalisé. Le comparateur définit l'ordre des éléments.
• Arrays.parallelSort(Array) : Cette version de la méthode trie le tableau en parallèle, en utilisant plusieurs threads pour améliorer les performances. C'est bénéfique pour trier de grands tableaux.
• Arrays.parallelSort(Array, fromIndex, toIndex) : Cette version surchargée de la méthode parallelSort permet de trier une plage spécifique d'éléments dans le Array .

Ils permettent d'organiser rapidement les éléments en fonction de leur ordre naturel ou à l'aide d'un comparateur personnalisé. Explorons cette méthode avec deux exemples, l'un impliquant des chaînes.

Exemple 1 : Tri des chaînes

Supposons que nous ayons une gamme d'instruments de musique à cordes : « violon », « alto », « violoncelle » et « contrebasse ». Nous pouvons utiliser la méthode Array.sort pour les classer par ordre alphabétique.

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

Le résultat est ici : Dans ce programme, nous importons d’abord la classe java.util.Arrays pour accéder à la méthode Array.sort . Ensuite, nous créons un tableau de chaînes appelé instruments contenant les noms des instruments de musique. Après cela, nous appelons Arrays.sort(instruments) . Ainsi, cette méthode obtient un tableau, trie les éléments par ordre croissant en fonction de leur ordre naturel (alphabétique). Enfin, nous parcourons le tableau trié et imprimons chaque instrument.

Exemple 2 : Trier des entiers

Prenons un autre exemple dans lequel nous trions un tableau d'entiers par ordre croissant.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Sortir: Ici, nous créons un tableau d'entiers appelé nombres avec plusieurs éléments non triés. Ensuite, nous appelons Arrays.sort(numbers) pour trier un tableau par ordre croissant. Notez que la méthode Array.sort modifie le tableau d'origine sur place. Donc, pour conserver le Array original , faites-en une copie avant de trier.

Exemple 3 : ordre décroissant

Et le tri décroissant ? C'est aussi facile avec Arrays.sort . Utilisez simplement un comparateur personnalisé. Voici un exemple :

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Le résultat est le suivant : Ici, nous avons un tableau d’entiers nommés nombres. En passant Comparator.reverseOrder() comme deuxième argument de la méthode Arrays.sort , nous spécifions un comparateur personnalisé qui trie les éléments par ordre décroissant. La méthode Comparator.reverseOrder() renvoie un comparateur qui inverse l'ordre naturel des éléments. Notez qu'ici, nous utilisons la classe wrapper Integer au lieu du type int primitif car la méthode Comparator.reverseOrder() nécessite des objets. Si vous disposez d'un tableau de valeurs int primitives, vous devrez également les convertir en objets Integer avant d'utiliser cette approche. À l'aide d'un comparateur personnalisé, vous pouvez facilement trier un tableau par ordre décroissant à l'aide de la méthode Arrays.sort en Java.

Algorithmes de tri classiques auto-écrits en Java

Vous avez déjà vu les devoirs de tri Array si vous étudiez l'informatique de manière indépendante ou à l'université. Il existe de nombreux algorithmes de tri différents, et nous en implémenterons certains dans cet article. Généralement, plus un algorithme est simple à mettre en œuvre, moins il est efficace. Les programmeurs mesurent l'efficacité des algorithmes en fonction du temps de fonctionnement et de la mémoire dépensée en ressources. Ce n'est pas le sujet de notre article, mais nous mentionnons qu'Arrays.sort en Java est un algorithme efficace.

Tri à bulles

Commençons par l’algorithme le plus populaire parmi les étudiants : le tri à bulles. C'est simple : l'algorithme compare deux éléments puis les échange s'ils sont dans le mauvais ordre, et ainsi de suite jusqu'à la fin du tableau. Il s'avère que des éléments plus petits "flottent" jusqu'à la fin du tableau , comme des bulles de soda vers le haut.

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Ici, la méthode prend un tableau d’entiers en entrée. La boucle externe va de 0 à n-1. Ici n est la taille du tableau. La boucle interne compare les éléments adjacents. Si l'ordre est erroné, la méthode les échange. Cette procédure est répétée jusqu'à ce que l'ensemble du tableau ait été trié. Voici un résultat de notre programme :

Tri de sélection

L'algorithme de sélection trie un tableau en recherchant à plusieurs reprises le plus petit élément de la partie non triée et en le plaçant au début. Écrivons-le en Java :

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

Voici un résultat du programme : Expliquons-le étape par étape. La boucle externe parcourt le début du tableau jusqu'à l'avant-dernier élément (jusqu'à n-1). Cette boucle sélectionne chaque élément un par un comme point de départ de la partie non triée du Array . À l'intérieur de la boucle externe, nous initialisons minIndex à l'index actuel i , en supposant qu'il s'agit de l'index du plus petit élément de la partie non triée du Array . La boucle interne commence à i+1 et monte jusqu'au dernier élément du Array . Il recherche l'index du plus petit élément dans la partie non triée du tableau en comparant chaque élément avec l'élément minimum actuel ( arr[minIndex] ). Si nous trouvons un élément plus petit que l'élément minimum actuel, nous mettons à jour minIndex avec l'index du nouvel élément minimum. Une fois la boucle interne terminée, nous avons trouvé l'index de l'élément minimum dans la partie non triée du Array . Nous échangeons ensuite l'élément minimum avec le premier élément de la partie non triée en utilisant une variable temporaire temp. La boucle externe continue jusqu'à ce que tous les éléments soient triés, étendant progressivement la partie triée du Array . Enfin, le tableau trié est imprimé dans la méthode main avant et après l'appel de la méthode selectionSort .

Tri par fusion

Merge Sort est un algorithme diviser pour régner qui divise de manière récursive le tableau en sous-tableaux plus petits, les trie, puis les fusionne pour obtenir un tableau trié. Le tri par fusion est stable et largement utilisé, en particulier lorsque la stabilité et une complexité temporelle garantie dans le pire des cas sont requises.

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

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

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

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

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Le résultat ici est : Expliquons plus précisément comment cela fonctionne. L'algorithme divise le tableau en deux parties de manière récursive jusqu'à ce que le cas de base soit atteint (lorsque le tableau comporte un ou zéro élément). Ensuite, il fusionne les moitiés triées ensemble à l’aide de la méthode de fusion. La méthode de fusion prend trois tableaux en entrée : le tableau d'origine et les sous-tableaux gauche et droit (gauche et droite). Il compare les éléments des sous-tableaux gauche et droit et les fusionne dans le tableau d' origine dans l'ordre trié.

Tri par insertion

Le tri par insertion fonctionne en insérant à plusieurs reprises un élément de la partie non triée dans sa position correcte dans la partie triée. Il fonctionne bien pour les petits ensembles de données ou les données presque triées.

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Le résultat du programme est comme d'habitude : Ici, la méthode insertionSort implémente l'algorithme de tri par insertion. Il parcourt le tableau et considère chaque élément comme une clé. Il compare la clé avec les éléments qui la précèdent et les avance d'une position s'ils sont plus grands, déplaçant ainsi les éléments pour laisser de la place à la clé dans la bonne position. La boucle externe parcourt du deuxième élément ( i = 1 ) au dernier élément du tableau. La boucle interne commence à partir de l'élément actuel ( arr[i] ) et recule ( j = i - 1 ) jusqu'à ce qu'elle trouve la position correcte pour la clé ou atteigne le début du Array . À l'intérieur de la boucle interne, si un élément ( arr[j] ) est supérieur à la clé, il est décalé d'une position vers l'avant ( arr[j + 1] = arr[j] ) pour faire de la place à la clé. Ce processus se poursuit jusqu'à ce que la position correcte de la clé soit trouvée. Une fois la boucle interne terminée, la clé est placée à la bonne position ( arr[j + 1] = key ). Dans la méthode main, un exemple de tableau est créé et imprimé avant et après le tri à l'aide de la méthode insertionSort .

Tri rapide

Quick Sort est un algorithme diviser pour régner qui sélectionne un élément pivot et partitionne le tableau autour du pivot. En règle générale, le tri rapide est plus rapide que le tri par fusion pour les ensembles de données de petite et moyenne taille en raison de ses faibles facteurs constants.

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Le résultat est ici : Nous avons donc ici trois méthodes pour implémenter le tri rapide. La méthode quickSort prend trois paramètres : le tableau à trier, l'indice bas du sous-tableau et l'indice haut du sous-tableau. Initialement, il vérifie si le sous-tableau comporte plusieurs éléments. Si tel est le cas, il sélectionne un pivot à l'aide de la méthode de partition, trie de manière récursive le sous-tableau avant le pivot et trie de manière récursive le sous-tableau après le pivot. La méthode de partition sélectionne le pivot comme dernier élément du sous-tableau ( arr[high] ). Il définit l'indice de partition (i) à l'indice bas moins 1. Il itère ensuite de l'indice bas à l'indice haut - 1 et vérifie si chaque élément est inférieur ou égal au pivot. Si tel est le cas, il échange l'élément avec l'élément à l'index de partition (i) et incrémente l'index de partition. Enfin, il échange l'élément pivot avec l'élément à l'index de partition + 1 et renvoie l'index de partition. La méthode de partition sélectionne le pivot comme dernier élément du sous-tableau ( arr[high] ). Il définit l'index de partition (i) sur l'index bas moins 1. Il itère ensuite de l'index bas à l'index haut - 1 et vérifie si chaque élément est plus petit ou égal au pivot. Si tel est le cas, il échange l'élément avec l'élément à l'index de partition (i) et incrémente l'index de partition. Enfin, il échange l'élément pivot avec l'élément à l'index de partition + 1 et renvoie l'index de partition. La méthode swap est une méthode utilitaire utilisée pour échanger deux éléments dans le Array . Dans la méthode principale , un exemple de tableau est créé et imprimé avant et après le tri à l'aide de la méthode quickSort .

Conclusions

Dans cet article, vous avez découvert comment trier un tableau en langage Java. Vous pouvez utiliser une méthode Arrays.sort intégrée ou écrire vos propres implémentations de méthodes de tri populaires telles que le tri à bulles, le tri par fusion, etc. Vous pouvez également essayer d’envahir votre propre méthode de tri. Cela dépend de votre tâche. Si vous avez besoin de résoudre rapidement un problème de tri, utilisez simplement une méthode pré-écrite. Si vous apprenez la programmation et essayez de vous améliorer, c'est une très bonne idée d'écrire vous-même des méthodes de tri.