Dans ce didacticiel, vous apprendrez comment fonctionne le tri à bulles. En outre, vous trouverez des exemples fonctionnels de tri à bulles en C, C ++, Java et Python.
Le tri à bulles est un algorithme qui compare les éléments adjacents et échange leurs positions s'ils ne sont pas dans l'ordre prévu. L'ordre peut être croissant ou décroissant.
Comment fonctionne le tri à bulles?
- À partir du premier index, comparez le premier et le deuxième élément.Si le premier élément est supérieur au deuxième, ils sont permutés.
Maintenant, comparez les deuxième et troisième éléments. Échangez-les s'ils ne sont pas en ordre.
Le processus ci-dessus se poursuit jusqu'au dernier élément.
Comparez les éléments adjacents - Le même processus se poursuit pour les itérations restantes. Après chaque itération, le plus grand élément parmi les éléments non triés est placé à la fin.
Dans chaque itération, la comparaison a lieu jusqu'au dernier élément non trié.
Le tableau est trié lorsque tous les éléments non triés sont placés à leurs positions correctes.
Comparez les éléments adjacents 
Comparez les éléments adjacents 
Comparez les éléments adjacents
Algorithme de tri à bulles
bubbleSort (array) for i rightElement swap leftElement et rightElement end bubbleSort
Exemples Python, Java et C / C ++
Python Java C C ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Tri à bulles optimisé
Dans le code ci-dessus, toutes les comparaisons possibles sont effectuées même si le tableau est déjà trié. Cela augmente le temps d'exécution.
Le code peut être optimisé en introduisant une variable supplémentaire permutée. Après chaque itération, s'il n'y a aucun échange en cours, il n'est pas nécessaire d'effectuer d'autres boucles.
Dans un tel cas, la variable permutée est définie sur false. Ainsi, nous pouvons empêcher d'autres itérations.
L'algorithme pour un tri optimisé des bulles est
bubbleSort (array) swapped <- false pour i rightElement swap leftElement et rightElement swapped <- true end bubbleSort
Exemples de tri à bulles optimisé
Python Java C C + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
// Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Complexité
Bubble Sort est l'un des algorithmes de tri les plus simples. Deux boucles sont implémentées dans l'algorithme.
| Cycle | Nombre de comparaisons |
|---|---|
| 1er | (n-1) |
| 2e | (n-2) |
| 3e | (n-3) |
| …. | … |
| dernier | 1 |
Nombre de comparaisons: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 presque égal à n 2
Complexité: O (n 2 )
De plus, nous pouvons analyser la complexité en observant simplement le nombre de boucles. Il y a 2 boucles donc la complexité estn*n = n2
Complexités temporelles:
-
Pire complexité des cas: Si nous voulons trier dans l'ordre croissant et que le tableau est dans l'ordre décroissant, le pire des cas se produit.
O(n2) -
Meilleure complexité des cas:
O(n)
si le tableau est déjà trié, aucun tri n'est nécessaire. -
Complexité moyenne des cas: elle se produit lorsque les éléments du tableau sont dans un ordre confus (ni croissant ni décroissant).
O(n2)
Complexité de l'espace:
La complexité de l'espace est O(1)due au fait qu'une température variable supplémentaire est utilisée pour l'échange.
Dans l'algorithme optimisé, la variable permutée ajoute ainsi à la complexité de l'espace, ce qui en fait O(2).
Applications de tri à bulles
Le tri à bulles est utilisé dans les cas suivants où
- la complexité du code n'a pas d'importance.
- un code court est préférable.
