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;
}

Enoncé exercice 3

Ecrire un programme C qui lit un tableau d’entiers et le trie en utilisant la méthode du tri par sélection.

Correction exercice 3

Le tri par sélection est une manière plus directe et plus intuitive pour le tri d’un tableau. Il consiste dans un premier temps à rechercher l’élément max dans tout le tableau pour le mettre dans la dernière case. Puis de chercher l’élément max dans le reste du tableau (en écartant la dernière case) pour le positionner dans l’avant dernière case et ainsi de suite en cherchant à chaque fois le max dans les éléments du tableau non encore positionnés.

On prend pour l’exemple le tableau suivant :

Le max de ce tableau est 9. On va le mettre dans la dernière case en le permutant avec celle-ci.

On cherche ensuite le max dans les éléments non positionnés, c’est-à-dire dans les cases blanches. Ce max est 7, on va le permuter avec l’avant dernière case. Ceci va donner :

Maintenant, le max dans les éléments non positionnés est le 5 et qui est déjà dans la bonne position.

Les configurations du tableau qui suivent seront comme suit :

Pour traduire cet algorithme en un programme, il suffira d’utiliser deux boucles for imbriquées. La première de compteur i va servir pour déterminer la position où on souhaite positionner le max. Et la deuxième va permettre de rechercher (sélectionner) l’élément max dans la plage des indices 0 à i (les deux inclus). Le max sera sélectionné en repérant sa position par jmax (lignes 12-17). Une fois le max sélectionné, on va le permuter avec la case d’indice i (lignes 18-20). De cette façon, il aura pris sa position définitive dans le tableau trié.

Dans le cas où le max est déjà dans la bonne position, on effectuera quand même la permutation, ce qui va résulter dans la permutation d’une variable avec elle-même. Comme ça, le max restera dans sa place et on aura évité d’introduire un test if, ce qui ne va qu’ajouter des lignes supplémentaires au programme.

Remarquez que le compteur i s’arrête à la valeur 1, car lorsque les éléments dans les cases 1 à n-1 ont pris leurs places, l’élément dans la case 0 aura aussi pris la seule place qui lui reste.

Solution exercice 3

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t[100];
	int i,j,n,jmax,tmp;
	printf("Entrez le 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--)
	{
	   jmax=0;
	   for(j=0;j<=i;j++)
	      if(t[j]>t[jmax])
	         jmax=j;
	    tmp=t[jmax];
	    t[jmax]=t[i];
	    t[i]=tmp;
	}
	printf("Tableau apres tri:\n");
	for(i=0;i<n;i++)
	   printf("%d ",t[i]);
	printf("\n");
	system("pause");
	return 0;
}

Enoncé exercice 4

Ecrire un programme C qui lit un tableau d’entiers, le trie puis affiche, dans un ordre croissant, tous les éléments qui y sont présents sans les répéter.

Exemple : pour le tableau suivant 2 4 3 5 5 9 2 9 on doit afficher 2 3 4 5 9.

Correction exercice 4

Dans ce programme, on va commencer par la lecture d’un tableau d’entiers. Puis on va le trier en utilisant un des divers algorithmes de tri (lignes 5-19).

Une fois le tableau trié, il est facile d’afficher les éléments qui constituent le tableau en évitant de répéter l’un d’eux. L’astuce pour ceci est simple. Il faudra dans un premier temps afficher le premier élément du tableau. Pour le restant des éléments, on va utiliser une boucle for pour les parcourir et afficher seulement les nombres qui sont différents des éléments qui les précèdent. En d’autres termes, on affichera l’élément t[i] si et seulement si t[i] est différents de t[i-1] (lignes 21-25). Ceci marche, puisque dans le tableau trié, les éléments répétés occupent des cases consécutives. Et de cette manière on vise à afficher leur première occurrence seulement.

Si on prend par exemple le tableau suivant :

Après son tri on aura :

La première case doit être toujours affichée :

Après, on cherche dans les autres cases celles qui sont précédées d’un élément d’une valeur différente.

Ce qui donnera les éléments constituant le tableau et qui sont : 1, 2, 3, 4 et 8.

Solution exercice 4

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t[100];
	int i,j,n,tmp;
	printf("Entrez le nombre d'elements:\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("Les entiers presents dans le tableau sont:\n");
	printf("%d",t[0]);
	for(i=1;i<n;i++)
	   if(t[i]!=t[i-1])
	      printf(" %d",t[i]);
	printf("\n");
	system("pause");
	return 0;
}

Enoncé exercice 5

Ecrire un programme C qui lit un tableau d’entiers à deux dimensions puis trie les éléments de chaque ligne indépendamment et l’affiche.

Correction exercice 5

Dans ce programme, on va lire un tableau t à deux dimensions puis on triera les éléments de chacune de ses lignes. N’importe quelle méthode de tri va permettre de réaliser cette opération. Ici, on a opté pour le tri à bulles pour ça simplicité.

Le tableau t a n lignes et m colonnes. On utilisera un compteur i pour parcourir ses lignes et réserver un compteur j pour le parcours de ses colonnes.

La démarche adoptée consiste à utiliser une boucle for de compteur i pour sélectionner les lignes (ligne 12). Chaque ligne d’indice i sera considérée comme un tableau à une dimension à m éléments. Ce tableau t[i] sera trié en utilisant les deux boucles for imbriquées nécessaires pour le tri à bulles. La première boucle de compteur k fixera la limite de chacun des multiples parcours de la boucle de compteur j (ligne 16). Cette dernière boucle, parcourt la ligne i en s’arrêtant avant d’arriver à l’indice k (lignes 17). Elle permet de comparer les éléments dans les cases adjacentes j et j+1 de la ligne i et de les permuter au cas où t[i][j] est supérieur à t[i][j+1] pour pouvoir ainsi trier la ligne i dans un ordre croissant (lignes 18-23).

Une fois qu’on sort des trois boucles imbriquées, toutes les lignes du tableau seront triées dans un ordre croissant. On pourra donc afficher le tableau pour visualiser le résultat (lignes 24-30).

Solution exercice 5

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t[20][20];
	int i,j,k,n,m,tmp;
	printf("Entrez le nombre de lignes:\n");
	scanf("%d",&n);
	printf("Entrez le nombre de colonnes:\n");
	scanf("%d",&m);
	printf("Entrez les elements du tableau:\n");
	for(i=0;i<n;i++)
	   for(j=0;j<m;j++)
	      scanf("%d",&t[i][j]);
	for(i=0;i<n;i++)
		for(k=m-1;k>0;k--)
	   		for(j=0;j<k;j++)
	      		if(t[i][j]>t[i][j+1])
	      		{
	      	 		tmp=t[i][j];
	      	 		t[i][j]=t[i][j+1];
	      	 		t[i][j+1]=tmp;
		  		}
	printf("Le tableau apres tri:\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
			printf("%d ",t[i][j]);
		printf("\n");
	}
	system("pause");
	return 0;
}