Enoncé exercice 1
Ecrire un programme C qui lit un tableau d’entiers et le tri dans un ordre croissant en utilisant le tri à bulles.
Correction exercice 1
Dans cet exercice il est demandé de trier un tableau d’entiers d’une manière croissante en utilisant le tri à bulles. Pour ça, on va lire dans un premier temps un tableau d’entiers t de nombre d’éléments n (lignes 7-11).
Le tri à bulles est effectué par la permutation des valeurs de toutes les cases adjacentes dans le tableau où celle d’indice inférieur a une valeur plus grande que celle de l’autre. La recherche de ces cases est réalisé selon un mode spécifique au tri à bulles. En plus, cette recherche est effectuée en plusieurs parcours du tableau.
Pour illustration, on va prendre l’exemple du tableau suivant, constitué de 5 éléments (n=5):
Dans un premier parcours, on va comparer chaque case avec celle qui la suit. Ceci va nécessiter l’utilisation d’une boucle à 4 itérations, car le tableau contient 4 cases adjacentes (les cases en vert).
Pour ce premier parcours, on aura besoin d’une boucle for de compteur j allant de 0 à 3 c’est-à-dire de 0 à n-2. Cette boucle sera utilisée pour comparer les cases t[j] et t[j+1] et effectuer la permutation dans le cas où t[j] est supérieur à t[j+1].
Après ce premier parcours, on peut remarquer que la valeur maximale du tableau sera positionnée dans la dernière case. Donc aucune valeur du tableau ne peut lui être supérieure, en particulier celle qui lui est adjacente. D’où il n’est plus nécessaire de la comparer avec cette case. Le prochain parcours contiendra alors seulement 3 itérations au lieu de 4.
Dans ce deuxième parcours, le compteur j doit aller de 0 à 2 qui est n-3, dans l’objectif de comparer les cases t[j] et t[j+1] et les permuter lorsque cela sera nécessaire.
Après ce parcours, le max des cases parcourues (le max ici est 4) se trouvera dans l’avant dernière case.
Le troisième et le quatrième parcours vont se dérouler comme suit :
Pour le dernier parcours, j ira de 0 à 0.
Les remarques faites dans cet exemple, peuvent être généralisées pour un tableau de taille n quelconque.
Les différents parcours utilisent un compteur j qui commence toujours à 0 et se terminent à n-2 pour le premier, n-3 pour le deuxième et ainsi de suite en décrémentant cette limite par 1 après chaque parcours jusqu’à atteindre 0. On va prendre comme limite du compteur j un autre compteur i dont la valeur sera changée par une autre boucle for.
Si on prend comme condition de réitération de la boucle de parcours, la condition j<i alors i doit aller de n-1 à 1 (ligne 12-13).
Solution exercice 1
#include<stdio.h>
#include<stdlib.h>
int main()
{
int t[100];
int i,j,n,tmp;
printf("Entrez la nombre des elements du tableau:\n");
scanf("%d",&n);
printf("Entrez les elements du tableau:\n");
for(i=0;i<n;i++)
scanf("%d",&t[i]);
for(i=n-1;i>0;i--)
for(j=0;j<i;j++)
if(t[j]>t[j+1])
{
tmp=t[j];
t[j]=t[j+1];
t[j+1]=tmp;
}
printf("Tableau trie:\n");
for(i=0;i<n;i++)
printf("%d ",t[i]);
printf("\n");
system("pause");
return 0;
}Enoncé exercice 2
Ecrire un programme C qui trie dans un ordre croissant les éléments d’un tableau d’entiers en utilisant le tri par insertion.
Correction exercice 2
Le tri par insertion se base sur l’idée que si pour un tableau t à n éléments, les éléments de l’indice 0 à i-1 sont triés dans un ordre croissant, il suffira pour trier les éléments de 0 à i d’insérer l’élément t[i] directement après le premier élément qui lui est inférieur, en commençant par la case i-1 et en se dirigeant vers les indices inférieurs.
Dans le tableau ci-dessous, les éléments de l’indice 0 à 3 sont triés dans un ordre croissant.
Afin d’élargir la partie triée pour qu’elle englobe la case d’indice 4, il faudra insérer la valeur de cette case qui est 3 juste après le premier élément qui lui est inférieur dans la zone triée, en commençant de la droite. Donc, 8 n’est pas inférieur à 3 et 5 non plus, mais 1 est inférieur à 3. Le 3 sera donc inséré directement après la case contenant 1.
En continuant de cette sorte, on va introduire à chaque fois une nouvelle case vers la zone triée et le tableau sera ainsi trié.
Au départ, la zone triée contiendra seulement la première case. Et le premier élément à examiner sera celui d’indice 1. Donc, on va utiliser pour le programme une boucle for de compteur i allant de 1 jusqu’au dernier élément, pour spécifier l’élément qu’on essaye d’insérer dans la zone triée (ligne 12). Au sein de cette boucle, on va commencer par l’affectation de la valeur t[i] à la variable a, car la valeur dans la case i sera écrasée lors du décalage nécessaire pour l’insertion. Puis on va utiliser une autre boucle pour rechercher le premier élément inférieur à a. Cette boucle aura un compteur j qui commencera à la case i-1 (ligne 14).
Cette deuxième boucle est une boucle while qui continuera donc à décrémenter j et décaler les cases d’un pas vers les indices supérieurs chaque fois que a est toujours inférieur à l’élément t[j], c’est-à-dire que l’élément inférieur à a n’est pas encore atteint. Bien évidemment, cette boucle va s’arrêter après que la première case est atteinte.
Lorsque cette boucle aura terminé, ça voudra dire une de deux choses, soit l’élément t[j] est inférieur à a, donc on l’insérera dans la case j+1 (juste après t[j]) ou que j est devenu inférieur à 0, c’est-à-dire que j est égal à -1, dans ce cas a sera inséré à la case d’indice 0 qui correspond aussi à la case j+1. Donc, dans les deux cas, a sera affecté à la case j+1 (ligne 21).
On termine le programme en affichant le tableau trié (lignes 23-26).
Solution exercice 2
#include<stdio.h>
#include<stdlib.h>
int main()
{
int t[100];
int i,j,n,a;
printf("Donnez le nombre d'elements du tableau:\n");
scanf("%d",&n);
printf("Entrez les elements du tableau:\n");
for(i=0;i<n;i++)
scanf("%d",&t[i]);
for(i=1;i<n;i++)
{
j=i-1;
a=t[i];
while(a<t[j] && j>=0)
{
t[j+1]=t[j];
j--;
}
t[j+1]=a;
}
printf("Le tableau trie:\n");
for(i=0;i<n;i++)
printf("%d ",t[i]);
printf("\n");
system("pause");
return 0;
}