Structure des données - Algorithme de tri à bulles

Le tri à bulles est un algorithme de tri simple. Cet algorithme de tri est un algorithme basé sur la comparaison dans lequel chaque paire d'éléments adjacents est comparée et les éléments sont échangés s'ils ne sont pas dans l'ordre. Cet algorithme ne convient pas aux grands ensembles de données car sa complexité moyenne et dans le pire des cas est de Ο (n ² ) oùn est le nombre d'éléments.

Comment fonctionne le tri à bulles?

Nous prenons un tableau non trié pour notre exemple. Le tri des bulles prend Ο (n ² ) temps, nous le gardons donc court et précis.

Le tri à bulles commence par les deux premiers éléments, en les comparant pour vérifier lequel est le plus grand.

Dans ce cas, la valeur 33 est supérieure à 14, elle se trouve donc déjà dans des emplacements triés. Ensuite, nous comparons 33 à 27.

Nous trouvons que 27 est inférieur à 33 et ces deux valeurs doivent être permutées.

Le nouveau tableau devrait ressembler à ceci -

Ensuite, nous comparons 33 et 35. Nous constatons que les deux sont dans des positions déjà triées.

Ensuite, nous passons aux deux valeurs suivantes, 35 et 10.

Nous savons alors que 10 est plus petit 35. Par conséquent, ils ne sont pas triés.

Nous échangeons ces valeurs. Nous constatons que nous avons atteint la fin du tableau. Après une itération, le tableau devrait ressembler à ceci -

Pour être précis, nous montrons maintenant à quoi doit ressembler un tableau après chaque itération. Après la deuxième itération, cela devrait ressembler à ceci -

Notez qu'après chaque itération, au moins une valeur se déplace à la fin.

Et quand aucun échange n'est requis, le tri par bulles apprend qu'un tableau est complètement trié.

Nous devrions maintenant examiner certains aspects pratiques du tri à bulles.

Algorithme

Nous supposons list est un tableau de néléments. Nous supposons en outre queswap function permute les valeurs des éléments de tableau donnés.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

Pseudocode

Nous observons dans l'algorithme que Bubble Sort compare chaque paire d'éléments de tableau à moins que le tableau entier ne soit complètement trié dans un ordre croissant. Cela peut entraîner quelques problèmes de complexité comme si le tableau n'a plus besoin d'être permuté car tous les éléments sont déjà ascendants.

Pour résoudre le problème, nous utilisons une variable d'indicateur swappedce qui nous aidera à voir si un échange a eu lieu ou non. Si aucun échange n'a eu lieu, c'est-à-dire que le tableau ne nécessite plus de traitement pour être trié, il sortira de la boucle.

Le pseudocode de l'algorithme BubbleSort peut être écrit comme suit -

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

la mise en oeuvre

Un autre problème que nous n'avons pas abordé dans notre algorithme d'origine et son pseudo-code improvisé, est que, après chaque itération, les valeurs les plus élevées s'établissent à la fin du tableau. Par conséquent, la prochaine itération n'a pas besoin d'inclure des éléments déjà triés. Pour cela, dans notre implémentation, nous restreignons la boucle interne pour éviter les valeurs déjà triées.

Pour en savoir plus sur l'implémentation du tri à bulles dans le langage de programmation C, veuillez cliquer ici .