Tri à bulles en Java

1. Introduction

Dans cet article rapide, nous explorerons en détail l'algorithme Bubble Sort, en nous concentrant sur une implémentation Java.

C'est l'un des algorithmes de tri les plus simples; l'idée principale est de continuer à permuter les éléments adjacents d'un tableau s'ils sont dans un ordre incorrect jusqu'à ce que la collection soit triée.

Les petits éléments «remontent» en haut de la liste lorsque nous itérons la structure des données. Par conséquent, la technique est connue sous le nom de tri à bulles.

Comme le tri est effectué par échange, nous pouvons dire qu'il effectue un tri sur place.

De plus, si deux éléments ont les mêmes valeurs, les données résultantes verront leur ordre conservé - ce qui en fait un tri stable.

2. Méthodologie

Comme mentionné précédemment, pour trier un tableau, nous le parcourons en comparant les éléments adjacents et en les échangeant si nécessaire. Pour un tableau de taille n , nous effectuons n-1 de telles itérations.

Prenons un exemple pour comprendre la méthodologie. Nous aimerions trier le tableau dans l'ordre croissant:

4 2 1 6 3 5

Nous commençons la première itération en comparant 4 et 2; ils ne sont certainement pas dans le bon ordre. L'échange entraînerait:

[2 4] 1 6 3 5

Maintenant, répétez la même chose pour 4 et 1:

2 [1 4] 6 3 5

Nous continuons à le faire jusqu'à la fin:

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

Comme nous pouvons le voir, à la fin de la première itération, nous avons obtenu le dernier élément à sa juste place. Maintenant, tout ce que nous avons à faire est de répéter la même procédure dans d'autres itérations. Sauf, nous excluons les éléments qui sont déjà triés.

Dans la deuxième itération, nous allons parcourir tout le tableau à l'exception du dernier élément. De même, pour la 3ème itération, nous omettons les 2 derniers éléments. En général, pour la k-ième itération, nous itérons jusqu'à l'index nk (exclu). À la fin des n-1 itérations, nous obtiendrons le tableau trié.

Maintenant que vous comprenez la technique, plongeons dans l'implémentation.

3. Mise en œuvre

Implémentons le tri pour l'exemple de tableau dont nous avons discuté en utilisant l'approche Java 8:

void bubbleSort(Integer[] arr) { int n = arr.length; IntStream.range(0, n - 1) .flatMap(i -> IntStream.range(1, n - i)) .forEach(j -> { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } }); }

Et un test rapide JUnit pour l'algorithme:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }

4. Complexité et optimisation

Comme on peut le voir, pour la moyenne et le pire des cas , la complexité temporelle est O (n ^ 2) .

De plus, la complexité de l'espace , même dans le pire des scénarios, est de O (1) car l'algorithme de tri à bulles ne nécessite aucune mémoire supplémentaire et le tri a lieu dans le tableau d'origine.

En analysant soigneusement la solution, nous pouvons voir que si aucun échange n'est trouvé dans une itération, nous n'avons pas besoin d'itérer davantage .

Dans le cas de l'exemple discuté précédemment, après la 2ème itération, on obtient:

1 2 3 4 5 6

Dans la troisième itération, nous n'avons pas besoin d'échanger une paire d'éléments adjacents. Nous pouvons donc ignorer toutes les itérations restantes.

In case of a sorted array, swapping won't be needed in the first iteration itself – which means we can stop the execution. This is the best case scenario and the time complexity of the algorithm is O(n).

Now, let's implement the optimized solution.

public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (int j = 1; j  arr[j]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; swapNeeded = true; } } if(!swapNeeded) { break; } i++; } }

Let's check the output for the optimized algorithm:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }

5. Conclusion

In this tutorial, we saw how Bubble Sort works, and it's implementation in Java. We also saw how it can be optimized. To summarize, it's an in-place stable algorithm, with time complexity:

  • Worst and Average case: O(n*n), when the array is in reverse order
  • Best case: O(n), when the array is already sorted

L'algorithme est populaire en infographie, en raison de sa capacité à détecter quelques petites erreurs de tri. Par exemple, dans un tableau presque trié, seuls deux éléments doivent être échangés pour obtenir un tableau complètement trié. Bubble Sort peut corriger de telles erreurs (c'est-à-dire trier ce tableau) en temps linéaire.

Comme toujours, le code pour l'implémentation de cet algorithme se trouve à l'adresse over sur GitHub.