Dans cet article, nous aborderons l’algorithme de tri à bulles. La procédure de travail du tri à bulles est la plus simple. Cet article sera très utile et intéressant pour les étudiants car ils pourraient être confrontés au tri à bulles comme question lors de leurs examens. Il est donc important d’aborder le sujet.
convertir un entier en chaîne C++
Le tri à bulles fonctionne sur l'échange répété d'éléments adjacents jusqu'à ce qu'ils ne soient pas dans l'ordre prévu. C'est ce qu'on appelle le tri à bulles car le mouvement des éléments du tableau est similaire au mouvement des bulles d'air dans l'eau. Les bulles d’eau remontent à la surface ; de même, les éléments du tableau dans le tri à bulles se déplacent vers la fin de chaque itération.
Bien qu’il soit simple à utiliser, il est principalement utilisé comme outil pédagogique car les performances du tri à bulles sont médiocres dans le monde réel. Il ne convient pas aux grands ensembles de données. La complexité moyenne et dans le pire des cas du tri à bulles est Sur2), où n est un certain nombre d'éléments.
Bubble short est principalement utilisé là où -
- la complexité n'a pas d'importance
- simple et shortcode est préféré
Algorithme
Dans l'algorithme donné ci-dessous, supposons arr est un tableau de n éléments. L'assumé échanger La fonction dans l'algorithme échangera les valeurs des éléments du tableau donnés.
begin BubbleSort(arr) for all array elements if arr[i] > arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort
Fonctionnement de l'algorithme de tri à bulles
Voyons maintenant le fonctionnement de l'algorithme de tri à bulles.
Pour comprendre le fonctionnement de l'algorithme de tri à bulles, prenons un tableau non trié. Nous prenons un tableau court et précis, car nous savons que la complexité du tri à bulles est Sur2).
Soit les éléments du tableau -
Premier passage
Le tri commencera à partir des deux éléments initiaux. Comparons-les pour vérifier lequel est le plus grand.
Ici, 32 est supérieur à 13 (32 > 13), donc il est déjà trié. Maintenant, comparez 32 avec 26.
Ici, 26 est plus petit que 36. Un échange est donc nécessaire. Après avoir échangé, le nouveau tableau ressemblera à -
Maintenant, comparez 32 et 35.
Ici, 35 est supérieur à 32. Aucun échange n’est donc requis car ils sont déjà triés.
Désormais, la comparaison se situera entre 35 et 10.
Ici, 10 est inférieur à 35 qui ne sont pas triés. Un échange est donc nécessaire. Nous arrivons maintenant à la fin du tableau. Après le premier passage, le tableau sera -
Passons maintenant à la deuxième itération.
Deuxième passe
Le même processus sera suivi pour la deuxième itération.
fichier .tif
Ici, 10 est inférieur à 32. Un échange est donc nécessaire. Après l'échange, le tableau sera -
Passons maintenant à la troisième itération.
Troisième passe
Le même processus sera suivi pour la troisième itération.
Ici, 10 est inférieur à 26. Un échange est donc nécessaire. Après l'échange, le tableau sera -
Passons maintenant à la quatrième itération.
Quatrième passage
De même, après la quatrième itération, le tableau sera -
Par conséquent, aucun échange n’est requis, le tableau est donc complètement trié.
Complexité du tri à bulles
Voyons maintenant la complexité temporelle du tri à bulles dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale du tri à bulles.
1. Complexité temporelle
| Cas | Complexité temporelle |
|---|---|
| Meilleur cas | Sur) |
| Cas moyen | Sur2) |
| Pire cas | Sur2) |
2. Complexité spatiale
| Complexité spatiale | O(1) |
| Écurie | OUI |
- La complexité spatiale du tri à bulles est O(1). En effet, dans le tri à bulles, une variable supplémentaire est requise pour l'échange.
- La complexité spatiale du tri à bulles optimisé est O(2). En effet, deux variables supplémentaires sont requises dans le tri à bulles optimisé.
Parlons maintenant de l'algorithme de tri à bulles optimisé.
Algorithme de tri à bulles optimisé
Dans l'algorithme de tri à bulles, les comparaisons sont effectuées même lorsque le tableau est déjà trié. De ce fait, le temps d’exécution augmente.
Pour le résoudre, nous pouvons utiliser une variable supplémentaire échangé. Il est réglé sur vrai si l'échange l'exige ; sinon, il est réglé sur FAUX.
Il sera utile, comme supposons qu'après une itération, si aucun échange n'est requis, la valeur de la variable échangé sera FAUX. Cela signifie que les éléments sont déjà triés et qu’aucune autre itération n’est requise.
Cette méthode réduira le temps d’exécution et optimisera également le tri des bulles.
Algorithme pour un tri à bulles optimisé
bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] > array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort
Implémentation du tri à bulles
Voyons maintenant les programmes de tri Bubble dans différents langages de programmation.
séquence de fibonacci java
Programme: Écrivez un programme pour implémenter le tri à bulles en langage C.
#include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are -
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are -
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
before sorting array elements are -
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>'); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - ' + ' <br>'); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;> Sortir
Programme: Écrivez un programme pour implémenter le tri à bulles en PHP.
<?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>'; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>'; printArray($a); ?> </5;> Sortir
Programme: Écrivez un programme pour implémenter le tri à bulles en python.
a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print(\' after sorting array elements are - \') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:>