DAA - Tri à bulles

Bubble Sort est un algorithme de tri élémentaire, qui fonctionne en échangeant à plusieurs reprises des éléments adjacents, si nécessaire. Lorsqu'aucun échange n'est requis, le fichier est trié.

Il s'agit de la technique la plus simple parmi tous les algorithmes de tri.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

la mise en oeuvre

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Une analyse

Ici, le nombre de comparaisons est

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n2)

Clairement, le graphique montre le n2 nature de la sorte de bulle.

Dans cet algorithme, le nombre de comparaison est indépendant de l'ensemble de données, c'est-à-dire que les éléments d'entrée fournis sont dans l'ordre trié ou dans l'ordre inverse ou au hasard.

Mémoire nécessaire

D'après l'algorithme indiqué ci-dessus, il est clair que le tri à bulles ne nécessite pas de mémoire supplémentaire.

Exemple

Unsorted list:
5 2 1 4 3 sept 6

1 er itération:

5 > 2 swap
2 5 1 4 3 sept 6

5 > 1 swap
2 1 5 4 3 sept 6

5 > 4 swap
2 1 4 5 3 sept 6

5 > 3 swap
2 1 4 3 5 sept 6

5 < 7 no swap
2 1 4 3 5 sept 6

7 > 6 swap
2 1 4 3 5 6 sept

2 ème itération:

2 > 1 swap
1 2 4 3 5 6 sept

2 < 4 no swap
1 2 4 3 5 6 sept

4 > 3 swap
1 2 3 4 5 6 sept

4 < 5 no swap
1 2 3 4 5 6 sept

5 < 6 no swap
1 2 3 4 5 6 sept

Il n'y a pas de changement de 3 e , 4 e , 5 e et 6 e itération.

Finalement,

the sorted list is
1 2 3 4 5 6 sept