Bubble sort en Java - trier un tableau d'entiers
L'algorithme de tri à bulles ou Bubble sort en anglais est l'un des algorithmes classique qui est utiliser pour expliquer le tri durant les cours à l'université. Il est aussi utiliser dans les exercices de C ou de C++ grace à sa simplicité. Vous entendez souvent sur comment écrire un programme qui fait le tri d'un tableau en utilisant l'algorithme Bubble sort pour trier un tableau d'entiers dans l'ordre croissant ou décroissant.
Dans l'algorithme Bubble sort, le tri d'un tableau non ordonné commence par le premier élément et le comparer avec l'élément adjacent et s'il est plus grand, on les permute. En faisant ça, on obtient le plus grand nombre à la fin après la première itération. Alors pour n éléments, il faut n-1 itérations et n-1 comparaisons au maximum et s'effectue en une complexité qui est égale à O(n²), ce qui le rend moins utilisable lorsque le tri se fait sur un tableau qui contient un très grand nombre d'éléments. Dans ce cas, il devient l'algorithme de tri le plus lent et le plus lourd, ce qui le classe parmi les mauvais algorithmes de tri. Voyons étape par étape dans cet exemple pour trier un tableau en utilisant le tri à bulles, comme on a dit après chaque étape le plus grand nombre est trié.
Références:
Java program to bubble sort
Bubble Sort Algorithm in Java with Example
Dans l'algorithme Bubble sort, le tri d'un tableau non ordonné commence par le premier élément et le comparer avec l'élément adjacent et s'il est plus grand, on les permute. En faisant ça, on obtient le plus grand nombre à la fin après la première itération. Alors pour n éléments, il faut n-1 itérations et n-1 comparaisons au maximum et s'effectue en une complexité qui est égale à O(n²), ce qui le rend moins utilisable lorsque le tri se fait sur un tableau qui contient un très grand nombre d'éléments. Dans ce cas, il devient l'algorithme de tri le plus lent et le plus lourd, ce qui le classe parmi les mauvais algorithmes de tri. Voyons étape par étape dans cet exemple pour trier un tableau en utilisant le tri à bulles, comme on a dit après chaque étape le plus grand nombre est trié.
Implémentation de tri à bulles en Java
Voici un programme Java qui implémente l'algorithme tri à bulles (Bubble sort).public class tri_a_bulles_array{
public static void main(String[] args) {
int T[] = {99, 45, 68, 18, 34, 26, 50, 8, 55, 10};
System.out.print("Avant le tri ");
for (int n:T)
System.out.print(n+" ");
T = tri_a_bulles(T);
System.out.print("\nAprès le tri ");
for (int n:T)
System.out.print(n+" ");
}
static int[] tri_a_bulles(int T[])
{
int temp;
for(int i = T.length-1 ; i>=1 ; i--)
{
for(int j = 0 ; j<i ; j++)
if(T[j] > T[j+1])
{
temp = T[j+1];
T[j+1]=T[j];
T[j]=temp;
}
}
return T;
}
}
Voyons ce que ce programme donne: Avant le tri 99 45 68 18 34 26 50 8 55 10Vous pouvez aller plus loin voir des méthodes de tri prédéfinies en Java de la classe java.util.Arrays qui sont Arrays.sort() et Collections.sort().
Après le tri 8 10 18 26 34 45 50 55 68 99
Références:
Java program to bubble sort
Bubble Sort Algorithm in Java with Example