Introduction
Le tri est une opération courante dans la programmation. Il consiste à réorganiser les éléments d’un tableau dans un ordre spécifique. Le tri est utilisé pour améliorer l’efficacité des algorithmes de recherche, pour afficher des données dans un ordre logique ou pour effectuer des opérations mathématiques. Java dispose de plusieurs algorithmes de tri intégrés qui peuvent être utilisés pour trier des tableaux rapidement et facilement. Dans cet article, nous allons explorer les différentes manières de trier un tableau en Java, en utilisant des astuces et des exemples concrets.
Tri d’un tableau en Java
Java offre plusieurs façons de trier un tableau. Les algorithmes de tri intégrés dans Java sont les suivants :
- Tri à bulles
- Tri par sélection
- Tri par insertion
- Tri rapide
- Tri de fusion
- Tri de coquille
- Tri de tas
Chacun de ces algorithmes de tri a ses avantages et ses inconvénients en termes de complexité temporelle, de complexité spatiale et de stabilité. Dans la plupart des cas, le choix de l’algorithme de tri dépendra de la taille du tableau à trier et de la nature des données qu’il contient.
Tri à bulles
Le tri à bulles est l’un des algorithmes de tri les plus simples et les plus intuitifs. Il consiste à parcourir le tableau plusieurs fois, en comparant deux éléments consécutifs et en les échangeant si nécessaire. À chaque itération, le plus grand élément est déplacé vers la fin du tableau. Le tri à bulles a une complexité temporelle de O(n²) dans le pire des cas et de O(n) dans le meilleur des cas, où n est la taille du tableau.
Voici un exemple de tri à bulles en Java :
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}Ce code trie un tableau d’entiers en utilisant le tri à bulles. La méthode bubbleSort prend en paramètre un tableau d’entiers et modifie le tableau d’origine en le triant.
Tri par sélection
Le tri par sélection est un autre algorithme de tri simple. Il consiste à parcourir le tableau plusieurs fois, en sélectionnant le plus petit élément à chaque itération et en le plaçant au début du tableau. Le tri par sélection a une complexité temporelle de O(n²) dans tous les cas, où n est la taille du tableau.
Voici un exemple de tri par sélection en Java :
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}Ce code trie un tableau d'entiers en utilisant le tri par sélection. La méthode selectionSort prend en paramètre un tableau d'entiers et modifie le tableau d'origine en le triant.
Tri par insertion
Le tri par insertion est un troisième algorithme de tri simple. Il consiste à parcourir le tableau plusieurs fois, en insérant chaque élément à sa place correcte dans le sous-tableau déjà trié. Le tri par insertion a une complexité temporelle de O(n²) dans le pire des cas et de O(n) dans le meilleur des cas, où n est la taille du tableau.
Voici un exemple de tri par insertion en Java :
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}Ce code trie un tableau d’entiers en utilisant le tri par insertion. La méthode insertionSort prend en paramètre un tableau d’entiers et modifie le tableau d’origine en le triant.
Tri rapide
Le tri rapide est l’un des algorithmes de tri les plus rapides et les plus populaires. Il utilise une approche de diviser pour régner, en divisant le tableau en sous-tableaux plus petits et en triant chacun d’entre eux récursivement. Le tri rapide a une complexité temporelle moyenne de O(n log n) et une complexité spatiale de O(log n), où n est la taille du tableau.
Voici un exemple de tri rapide en Java :
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}Ce code trie un tableau d'entiers en utilisant le tri rapide. La méthode quickSort prend en paramètre un tableau d'entiers, la position de l'élément le plus petit et la position de l'élément le plus grand, et modifie le tableau d'origine en le triant. La méthode partition est une fonction auxiliaire qui partitionne le tableau en deux sous-tableaux, en utilisant un élément pivot.
Tri de fusion
Le tri de fusion est un autre algorithme de tri efficace qui utilise une approche de diviser pour régner. Il consiste à diviser le tableau en sous-tableaux plus petits, en les triant récursivement, puis en fusionnant les sous-tableaux triés. Le tri de fusion a une complexité temporelle moyenne de O(n log n) et une complexité spatiale de O(n), où n est la taille du tableau.
Voici un exemple de tri de fusion en Java :
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
public static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}Ce code trie un tableau d’entiers en utilisant le tri de fusion. La méthode mergeSort prend en paramètre un tableau d’entiers, la position de l’élément le plus petit et la position de l’élément le plus grand, et modifie le tableau d’origine en le triant. La méthode merge est une fonction auxiliaire qui fusionne deux sous-tableaux triés en un seul tableau trié.
Tri de coquille
Le tri de coquille est un algorithme de tri qui utilise une approche de tri par insertion, en triant des sous-tableaux de manière incrémentale. Il consiste à trier les éléments du tableau à des écarts définis, en réduisant progressivement les écarts jusqu’à atteindre un écart de 1, qui correspond à un tri par insertion standard. Le tri de coquille a une complexité temporelle moyenne de O(n log n) et une complexité spatiale de O(1), où n est la taille du tableau.
Voici un exemple de tri de coquille en Java :
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n/2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i += 1) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}Ce code trie un tableau d’entiers en utilisant le tri de coquille. La méthode shellSort prend en paramètre un tableau d’entiers et modifie le tableau d’origine en le triant.
Tri de tas
Le tri de tas est un algorithme de tri basé sur les tas binaires. Il consiste à construire un arbre binaire qui satisfait la propriété de tas, en triant ensuite les éléments en utilisant la structure de tas. Le tri de tas a une complexité temporelle moyenne de O(n log n) et une complexité spatiale de O(1), où n est la taille du tableau.
Voici un exemple de tri de tas en Java :
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n-1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}Ce code trie un tableau d’entiers en utilisant le tri de tas. La méthode heapSort prend en paramètre un tableau d’entiers et modifie le tableau d’origine en le triant. La méthode heapify est une fonction auxiliaire qui maintient la propriété de tas lors de la construction de l’arbre binaire.
Conclusion
Dans cet article, nous avons examiné les différentes façons de trier un tableau en Java, en utilisant des astuces et des exemples concrets. Nous avons vu que Java offre plusieurs algorithmes de tri intégrés qui peuvent être utilisés pour trier des tableaux rapidement et facilement. Chacun de ces algorithmes de tri a ses avantages et ses inconvénients en termes de complexité temporelle, de complexité spatiale et de stabilité. Le choix de l’algorithme de tri dépendra de la taille du tableau à trier et de la nature des données qu’il contient. En utilisant les astuces et les exemples présentés ici, vous pouvez trier facilement un tableau en Java et améliorer les performances de votre code.
Note : Cet article n'est pas mis à jour régulièrement et peut contenir des informations obsolètes ainsi que des erreurs.
