bubble sort c with examples
Technique de tri à bulles en C ++.
Bubble Sort est la plus simple des techniques de tri.
Dans la technique de tri à bulles, chacun des éléments de la liste est comparé à son élément adjacent. Ainsi, s'il y a n éléments dans la liste A, alors A [0] est comparé à A [1], A [1] est comparé à A [2] et ainsi de suite.
Après avoir comparé si le premier élément est supérieur au second, les deux éléments sont alors échangés.
=> Visitez ici pour le cours C ++ complet d'experts.
Ce que vous apprendrez:
implémentation de table de hachage dans le code C ++
- Technique de tri à bulles
- Illustration
- Exemple C ++
- Exemple Java
- Analyse de complexité de l'algorithme de tri à bulles
- Conclusion
- lecture recommandée
Technique de tri à bulles
En utilisant la technique de tri à bulles, le tri se fait par passes ou itérations. Ainsi, à la fin de chaque itération, l'élément le plus lourd est placé à sa place dans la liste. En d'autres termes, le plus grand élément de la liste bouillonne.
Nous avons donné ci-dessous un algorithme général de la technique de tri des bulles.
Algorithme général
Étape 1 : Pour i = 0 à N-1, répétez l'étape 2
Étape 2 : Pour J = i + 1 à N - je répète
Étape 3 : si A [J]> A [i]
Permuter A [J] et A [i]
[Fin de la boucle interne pour]
[End if Outer for loop]
Étape 4 : Sortir
Voici un pseudo-code pour l'algorithme de tri à bulles, où nous parcourons la liste en utilisant deux boucles itératives.
Dans la première boucle, on part du 0eélément et dans la boucle suivante, nous partons d'un élément adjacent. Dans le corps de la boucle interne, nous comparons chacun des éléments adjacents et les échangeons s'ils ne sont pas dans l'ordre. À la fin de chaque itération de la boucle externe, l'élément le plus lourd bouillonne à la fin.
Pseudocode
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array[i-1] > array[i] then swap array[i-1] and array[i] swapped = true end if end for until not swapped end procedure
Ce qui précède est le pseudo-code de la technique de tri à bulles. Illustrons maintenant cette technique en utilisant une illustration détaillée.
Illustration
Nous prenons un tableau de taille 5 et illustrons l'algorithme de tri des bulles.
Tableau entièrement trié.
L'illustration ci-dessus peut être résumée sous forme de tableau comme indiqué ci-dessous:
Passe | Liste non triée | Comparaison | Liste triée |
---|---|---|---|
{5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
1 | {10,5,15,0,12} | {10,5} | {5,10,15,0,12} |
{5,10,15,0,12} | {10.15} | {5,10,15,0,12} | |
{5,10,15,0,12} | {15,0} | {5,10,0,15,12} | |
{5,10,0,15,12} | {15.12} | {5,10,0,12,15} | |
deux | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
{5,10,0,12,15} | {10.0} | {5,0,10,12,15} | |
3 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
{5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
{5,0,10,12,15} | TRIÉ |
Comme le montre l'illustration, à chaque passage, le plus grand élément bouillonne jusqu'au dernier, triant ainsi la liste à chaque passage. Comme mentionné dans l'introduction, chaque élément est comparé à son élément adjacent et interverti les uns avec les autres s'ils ne sont pas dans l'ordre.
Ainsi, comme le montre l'illustration ci-dessus, à la fin de la première passe, si le tableau doit être trié par ordre croissant, le plus grand élément est placé à la fin de la liste. Pour la deuxième passe, le deuxième élément le plus grand est placé à l'avant-dernière position dans la liste et ainsi de suite.
Lorsque nous atteignons N-1 (où N est un nombre total d'éléments dans la liste), nous aurons la liste entière triée.
comment débuter sa carrière dans les tests de logiciels
La technique de tri à bulles peut être implémentée dans n'importe quel langage de programmation. Nous avons implémenté l'algorithme de tri à bulles en utilisant le langage C ++ et Java ci-dessous.
Exemple C ++
Voyons un exemple de programmation pour démontrer le tri à bulles.
#include using namespace std; int main () { int i, j,temp,pass=0; int a[10] = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < Production:
Liste d'entrée…
10 2 0 14 43 25 18 1 5 45
Liste des éléments triés…
0 1 2 5 10 14 18 25 43 45
Nombre de passes prises pour trier la liste: 10
Exemple Java
class Main { public static void main(String[] args) { int pass = 0; int[] a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a[i] + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a[i] Production:
Dans les deux programmes, nous avons utilisé un tableau de 10 éléments et nous le trions en utilisant la technique du tri à bulles. Dans les deux programmes, nous avons utilisé deux boucles for pour parcourir les éléments adjacents du tableau.
À la fin de chaque passe (boucle externe), le plus grand élément du tableau est remonté jusqu'à la fin du tableau. Nous comptons également le nombre de passes nécessaires pour trier l'ensemble du tableau.
Analyse de complexité de l'algorithme de tri à bulles
A partir du pseudo code et de l'illustration que nous avons vu ci-dessus, en tri à bulles, nous faisons N-1 comparaisons dans la première passe, N-2 comparaisons dans la deuxième passe et ainsi de suite.
Par conséquent, le nombre total de comparaisons dans le tri à bulles est:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-1) / 2
= O (ndeux) => Complexité temporelle de la technique de tri à bulles
Ainsi, les diverses complexités de la technique de tri à bulles sont données ci-dessous:
Pire complexité temporelle des cas O (n 2) Meilleure complexité temporelle Sur) Complexité temporelle moyenne O (n 2) Complexité spatiale O (1)
La technique de tri à bulles ne nécessite qu'un seul espace mémoire supplémentaire pour la variable temp afin de faciliter l'échange. Par conséquent, la complexité spatiale de l'algorithme de tri des bulles est O (1).
Notez que la meilleure complexité temporelle pour la technique de tri à bulles sera lorsque la liste est déjà triée et que ce sera O (n).
Conclusion
Le principal avantage de Bubble Sort est la simplicité de l'algorithme. Dans le tri par bulles, à chaque passage, le plus grand élément bouillonne jusqu'à la fin de la liste si le tableau est trié par ordre croissant.
De même pour que la liste soit triée par ordre décroissant, le plus petit élément sera à sa place à la fin de chaque passage.
Étant la technique de tri la plus simple et la plus facile à mettre en œuvre, le tri à bulles est généralement utilisé pour présenter le tri au public. Deuxièmement, le tri à bulles est également utilisé dans des applications telles que l'infographie dans laquelle le remplissage des arêtes de polygone, etc. nécessite un tri à bulles pour trier les sommets bordant le polygone.
Dans notre prochain didacticiel, nous en apprendrons davantage sur le tri par sélection.
=> Visitez ici pour apprendre le C ++ à partir de zéro.
fusion du code source de tri c ++
lecture recommandée
- Shell tri en C ++ avec des exemples
- Sélection de tri en C ++ avec des exemples
- Méthode MongoDB Sort () avec exemples
- Commande de tri Unix avec syntaxe, options et exemples
- Tri par insertion en C ++ avec des exemples
- Fusionner le tri en C ++ avec des exemples
- Tri de tas en C ++ avec des exemples
- Tri rapide en C ++ avec des exemples