HOWTO · Java

Trier un tableau en Java sans utiliser la méthode sort()

Apprenez à trier un tableau en java sans utiliser la méthode sort()

Sur cette page

Vous pouvez trier un tableau Java sans appeler Arrays.sort() en comparant ses éléments et en les réordonnant vous-même. Cette approche est utile pour comprendre le fonctionnement du tri ou lorsqu’un exercice impose une implémentation manuelle. Arrays.toString() permet d’afficher un tableau, mais ne le trie pas.

Les exemples ci-dessous trient des tableaux d’entiers par ordre croissant. Bubble Sort, Selection Sort et Insertion Sort sont faciles à suivre, tandis que Merge Sort et Quicksort illustrent des approches récursives fondées sur le diviser pour régner. Chaque extrait de code est un programme Java complet. Selon les éléments d’exécution fournis, les cinq exemples produisent le même résultat : [11, 12, 22, 25, 34, 64, 90].

Trier un tableau en Java sans Arrays.sort()

Un algorithme de tri déplace les éléments d’un tableau jusqu’à ce qu’ils respectent l’ordre souhaité. Pour trier des entiers par ordre croissant, on peut comparer les valeurs et placer la plus petite avant la plus grande. Les algorithmes ci-dessous appliquent cette règle de différentes façons. Ils modifient le tableau d’origine sur place, sauf l’implémentation de Merge Sort, qui utilise des tableaux temporaires pendant la fusion.

Prenons {64, 34, 25, 12, 22, 11, 90} comme exemple de départ et visons {11, 12, 22, 25, 34, 64, 90}. Arrays.sort() est volontairement absent de chaque implémentation ; Arrays.toString() sert uniquement à formater le tableau pour l’affichage.

Tri à bulles

Bubble Sort effectue plusieurs parcours des paires d’éléments adjacents. Si la valeur de gauche est supérieure à celle de droite, il les échange. À la fin de chaque parcours complet, la plus grande valeur de la partie encore non triée a été déplacée à sa position finale. L’indicateur swapped interrompt la boucle plus tôt si un parcours n’entraîne aucun changement. Dans le pire des cas, le temps d’exécution est en O(n²) ; cette version convient donc surtout aux petits tableaux ou aux démonstrations.

Chaque extrait déclare une classe nommée Main : enregistrez et exécutez un seul exemple à la fois dans Main.java. Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void bubbleSort(int[] values) {
    for (int end = values.length - 1; end > 0; end--) {
      boolean swapped = false;
      for (int i = 0; i < end; i++) {
        if (values[i] > values[i + 1]) {
          int temp = values[i];
          values[i] = values[i + 1];
          values[i + 1] = temp;
          swapped = true;
        }
      }
      if (!swapped) {
        break;
      }
    }
  }
}
[11, 12, 22, 25, 34, 64, 90]

Tri par sélection

Selection Sort divise conceptuellement le tableau en un préfixe trié et les valeurs restantes, encore non triées. À chaque parcours, l’algorithme recherche la valeur minimale dans la partie non triée, puis l’échange avec le premier élément de cette partie. Par exemple, le premier parcours trouve 11 et le place à l’indice 0 ; le suivant trouve 12 pour l’indice 1. Le nombre de comparaisons est en O(n²), quel que soit l’ordre initial, mais le nombre d’échanges reste linéaire.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void selectionSort(int[] values) {
    for (int i = 0; i < values.length - 1; i++) {
      int minIndex = i;
      for (int j = i + 1; j < values.length; j++) {
        if (values[j] < values[minIndex]) {
          minIndex = j;
        }
      }
      int temp = values[i];
      values[i] = values[minIndex];
      values[minIndex] = temp;
    }
  }
}
[11, 12, 22, 25, 34, 64, 90]

Tri par insertion

Insertion Sort agrandit un préfixe trié de gauche à droite. L’algorithme enregistre la valeur suivante dans key, décale d’une position vers la droite les valeurs du préfixe qui lui sont supérieures, puis place la clé dans l’espace libéré. Au début de chaque parcours, tous les éléments situés avant i sont déjà triés. L’algorithme est facile à suivre et peut être efficace sur de petits tableaux ou des tableaux presque triés ; son temps d’exécution est en O(n²) dans le pire des cas.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void insertionSort(int[] values) {
    for (int i = 1; i < values.length; i++) {
      int key = values[i];
      int j = i - 1;
      while (j >= 0 && values[j] > key) {
        values[j + 1] = values[j];
        j--;
      }
      values[j + 1] = key;
    }
  }
}
[11, 12, 22, 25, 34, 64, 90]

Tri fusion

Merge Sort divise récursivement le tableau en deux jusqu’à ce que chaque partie ne contienne qu’une valeur, puis fusionne les parties triées. Pendant la fusion, deux indices suivent la prochaine valeur non utilisée de chaque moitié ; la plus petite est copiée en premier dans le résultat. En cas d’égalité, choisir la valeur de gauche préserve l’ordre relatif des éléments. Cette implémentation s’exécute en O(n log n) et alloue des tableaux temporaires au fil de la récursion : sa mémoire supplémentaire est donc proportionnelle à la taille de l’entrée.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    mergeSort(values);
    System.out.println(Arrays.toString(values));
  }

  static void mergeSort(int[] values) {
    if (values.length < 2) {
      return;
    }
    int middle = values.length / 2;
    int[] left = Arrays.copyOfRange(values, 0, middle);
    int[] right = Arrays.copyOfRange(values, middle, values.length);
    mergeSort(left);
    mergeSort(right);
    merge(values, left, right);
  }

  static void merge(int[] values, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        values[k++] = left[i++];
      } else {
        values[k++] = right[j++];
      }
    }
    while (i < left.length) values[k++] = left[i++];
    while (j < right.length) values[k++] = right[j++];
  }
}
[11, 12, 22, 25, 34, 64, 90]

Tri rapide

Quicksort choisit un pivot et partitionne la plage en cours : les valeurs inférieures au pivot sont placées avant lui et les autres après. Cette implémentation choisit comme pivot la dernière valeur. La méthode de partition renvoie l’indice final du pivot, puis des appels récursifs trient les plages situées de chaque côté. Quicksort s’exécute souvent en O(n log n), mais ce choix de pivot peut entraîner un temps en O(n²) sur des entrées défavorables, par exemple des données déjà ordonnées. Les appels récursifs utilisent également de l’espace sur la pile.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {64, 34, 25, 12, 22, 11, 90};
    quickSort(values, 0, values.length - 1);
    System.out.println(Arrays.toString(values));
  }

  static void quickSort(int[] values, int low, int high) {
    if (low >= high) {
      return;
    }
    int pivotIndex = partition(values, low, high);
    quickSort(values, low, pivotIndex - 1);
    quickSort(values, pivotIndex + 1, high);
  }

  static int partition(int[] values, int low, int high) {
    int pivot = values[high];
    int smallerEnd = low - 1;
    for (int current = low; current < high; current++) {
      if (values[current] < pivot) {
        smallerEnd++;
        int temp = values[smallerEnd];
        values[smallerEnd] = values[current];
        values[current] = temp;
      }
    }
    int pivotIndex = smallerEnd + 1;
    int temp = values[pivotIndex];
    values[pivotIndex] = values[high];
    values[high] = temp;
    return pivotIndex;
  }
}
[11, 12, 22, 25, 34, 64, 90]

Choisir un algorithme et comprendre ses compromis

Pour apprendre ou trier un petit tableau, Bubble Sort, Selection Sort et Insertion Sort rendent visibles chaque comparaison et chaque déplacement. Leur croissance quadratique les rend toutefois peu adaptés aux grandes entrées. Insertion Sort convient assez bien aux petits tableaux ou à ceux qui sont déjà presque ordonnés. Selection Sort peut être utile lorsque l’on veut limiter les écritures, car il effectue au plus un échange par parcours, même s’il examine encore toutes les valeurs restantes à chaque fois.

Merge Sort offre un temps d’exécution prévisible en O(n log n) et convient lorsque la stabilité du tri est utile, mais cette implémentation alloue des tableaux temporaires. Quicksort est souvent performant et trie dans le tableau d’origine ; cependant, cette version qui choisit le dernier élément comme pivot présente un cas défavorable en O(n²) et utilise la pile pour la récursion. En production, privilégiez les algorithmes de tri éprouvés de la bibliothèque Java, sauf si une exigence impose une implémentation manuelle. Pour trier des tableaux de types primitifs dans les cas courants, utilisez Arrays.sort() ; apprenez ou implémentez un algorithme manuel lorsque son fonctionnement ou les contraintes constituent le véritable objectif.