Programme C pour le tri à bulles : tri à bulles en C

introduction

Le tri d'un tableau tient une place d'une immense importance en informatique. Son utilité est remarquée lorsqu'il est nécessaire d'organiser les données dans un ordre spécifique. Il existe différents types d'algorithmes de tri. L'algorithme de tri le plus courant et le plus utilisé est le tri à bulles.

Tri à bulles en C

La technique utilisée pour le tri dans le tri à bulles est simple et facile à comprendre. Tout ce qu'il fait est de comparer l'élément actuel avec l'élément suivant et de l'échanger s'il est supérieur ou inférieur selon la condition. L'algorithme est très précis. Chaque fois qu'un élément est comparé à d'autres éléments jusqu'à ce que sa place soit trouvée, cela s'appelle une passe.

Cet algorithme est comparable aux bulles dans l'eau car il filtre le haut des bulles en forme de réseau. Parmi tous les algorithmes utilisés pour le tri, le tri à bulles est le plus simple et le plus lent avec une complexité temporelle de O(n^2). Cependant, l'algorithme peut être optimisé grâce à l'utilisation d'une variable indicateur qui quitte la boucle lorsque l'échange est terminé. Le meilleur cas pour le tri à bulles peut être O(n) lorsque le tableau est trié.

Par exemple, prenons un tableau non trié de cinq nombres comme indiqué ci-dessous

13, 32,26, 34,9

Le tri à bulles commencera à considérer les deux premiers éléments, et il les comparera pour vérifier lequel est le plus grand. Dans ce cas, 32 est supérieur à 13. Cette portion est donc déjà triée. Ensuite, nous comparons 32 à 26. Nous trouvons donc que 32 est supérieur à 26, donc ils doivent être échangés. Le nouveau tableau ressemblera à

13, 26, 32,34,9

Ensuite, nous comparons 32 et 34. Nous savons qu'ils sont déjà triés. On passe donc aux deux dernières variables 34 et 9. Comme 34 est supérieur à 9, il faut les échanger.

Nous échangeons les valeurs et arrivons à la fin du tableau après la première itération. Maintenant, le tableau ressemblera à

13, 26. 32,9,34

Après la deuxième itération, le tableau ressemblera à

13, 26, 9, 32, 34

Après la troisième itération, le tableau deviendra

13,9,26,32,34

Après la quatrième itération, le tableau sera complètement trié

9, 13, 26, 32, 34

Doit lire : Idées de projet en C

L'algorithme

Ici, nous supposons que le tableau a n éléments. De plus, nous supposons que la fonction de valeurs d'échange échange toutes les valeurs pour créer les numéros de tableau dans un ordre trié.

démarrer BubbleSort (tableau)

pour tous les éléments de la liste

si tableau[i]> tableau[i+1]

échanger des valeurs(array[i], array[i+1] )

fin si

fin pour

tableau de retour

fin du tri à bulles

Lire : Trier dans la structure des données : catégories et types

Pseudocode

Il est évident dans l'algorithme ci-dessus qu'il y a une comparaison entre chaque paire de l'élément de tableau jusqu'à ce que l'ensemble du tableau soit trié par ordre croissant. Cela peut entraîner quelques problèmes de complexité, tels que le résultat de l'algorithme lorsque le tableau est déjà trié par ordre croissant. Pour résoudre le problème, nous utiliserons une variable d'indicateur, ce qui nous permet de voir s'il y a eu un échange. Si plus aucun échange n'est nécessaire, nous sortirons de la boucle interne.

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

procédure BubbleSort (tableau : éléments du tableau)

itérer=tableau.nombre ;

pour k=0 pour itérer-1 faire :

drapeau = faux

pour l=0 pour itérer-1 faire :

si (tableau[l]> tableau[l+1]) alors

valeurs d'échange(tableau[l], tableau [l+1])

drapeau=vrai

fin si

fin pour

Si (non échangé) alors

Se rompre

Fin si

Fin pour

Tableau de retour de la procédure de fin

Essayons un exemple de programme de tri à bulles en C :

# inclure<stdio.h>

vide principal

{

int tableau [10], i, j, num

pour (i=0; i<=9; i++)

{

scanf("%d", &array[i])

}

pour(i=0;i<=9;i++)

{

pour(j=0;j<=9-i;j++)

{

si(tableau[j]>tableau[j+1])

{

num= tableau[j] ;

tableau[j]=tableau[j+1] ;

tableau[j+1]=num ;

}

}

}

printf("Le tableau trié est /n");

pour(i=0;i<=9;i++)

{

printf(“%d ”,&array[i])

}

}

Comme illustré dans l'exemple, cet algorithme de tri à bulles accepte 10 nombres de l'utilisateur et les stocke dans le tableau. Dans la partie suivante, il y a deux boucles for. La boucle externe s'exécute pour la valeur I, égale à zéro à moins qu'égale à neuf. La fonction de la boucle externe est de prendre en charge tous les éléments de la valeur qui doivent être comparés avec d'autres éléments.

Il y a une autre boucle à l'intérieur de la boucle extérieure. Il part de j=0 et court jusqu'à ce qu'il soit inférieur ou égal à huit. À l'intérieur, il y a une instruction conditionnelle if qui compare et vérifie si array[j] est supérieur à array [j+1]. Si la condition est satisfaite, les valeurs de array[j] et array [j+1] sont échangées.

Une variable du nom de num est utilisée à cette fin. Le premier array[j] est assigné à num, puis array[j+1] est assigné à array[j], et enfin num est assigné à array[j+1]. Ce processus se poursuivra jusqu'à ce que tous les éléments du tableau soient triés par ordre croissant. Après cela, le tableau trié est imprimé.

Implémentation optimisée de Bubble Sort

Nous avons un algorithme optimisé pour le tri à bulles pour améliorer les résultats. L'utilisation d'une variable drapeau effectue l'optimisation. La variable flag contiendra 1 s'il y a un échange, sinon elle sortira de la boucle. Vous trouverez ci-dessous le programme de tri à bulles optimisé en C.

#include<stdio.h>

vide principal

{

int array [10], i, j, num, flag=0 ;

pour (i=0; i<=9; i++)

{

scanf("%d", &array[i])

}

pour(i=0;i<=9;i++)

{

pour(j=0;j<=9-i;j++)

{

si(tableau[j]>tableau[j+1])

{

num= tableau[j] ;

tableau[j]=tableau[j+1] ;

tableau[j+1]=num ;

drapeau=1 ;

}

si (! drapeau)

{

Pause;

}

}

}

printf("Le tableau trié est /n");

pour(i=0;i<=9;i++)

{

printf(“%d ”,&array[i])

}

}

Le programme donné s'exécute d'une manière similaire au programme de tri à bulles normal. Le seul changement est l'utilisation de la variable flag. Initialement, le drapeau est mis à 0. Cependant, si un échange a lieu, le drapeau devient 1. Cela implique que le tableau nécessite encore une vérification supplémentaire. D'autre part, si le drapeau n'est pas 1, ce qui implique que l'échange n'a pas eu lieu, nous sortons de la boucle interne, en supposant que le tableau est déjà trié. Une fois exécuté, nous obtiendrons le même résultat que le tri Bubble normal.

Complexité temporelle

La complexité temporelle dans le meilleur des cas pour le tri à bulles est O(n). Cela se produit lorsque le tableau est déjà trié. Le pire des cas est O(n*n) lorsque le tableau n'a pas été trié.

Lis : Les 12 meilleurs programmes de modèles en Java que vous devriez vérifier aujourd'hui

Et ensuite ?

Si vous souhaitez en savoir plus sur Java, le développement de logiciels à pile complète, consultez le diplôme PG upGrad & IIIT-B en développement de logiciels à pile complète qui est conçu pour les professionnels en activité et offre plus de 500 heures de formation rigoureuse, plus de 9 projets et affectations, statut d'ancien de l'IIIT-B, projets de synthèse pratiques et aide à l'emploi avec les meilleures entreprises.