TP les types de trie en C
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
// tri par fusion
void fusion(int*t,int deb1,int fin1,int fin2)
{
int*table1;
int deb2=fin1+1;
int compt1=deb1;
int compt2=deb2;
int i;
table1=(int *)malloc((fin1-deb1+1)*sizeof(int));
for(i=deb1;i<=fin1;i++)
table1[i-deb1]=t[i];
for(i=deb1;i<=fin2;i++){
if( compt1==deb2) break;
else if (compt2==(fin2+1)) {
t[i]=table1[compt1-deb1];
compt1++;
}
else if(table1[ compt1- deb1] <t[ compt2]) {
t[i]=table1[compt1-deb1];
compt1++;
}
else{
t[i]=t[compt2];
compt2++;
}
}
free(table1);
}
void tri_fusion_T(int*t,int deb,int fin)
{
if(deb!=fin){
int milieu=( fin+deb) /2;
tri_fusion_T(t,deb,milieu);
tri_fusion_T(t,milieu+1,fin);
fusion(t,deb,milieu,fin);
}
}
void tri_fusion(int*t,int n)
{
if (n>0) tri_fusion_T(t,0,n-1);
}
// tri en bulle
void tri_en_bulle(int *t, int n)
{
int j =0 ;
int tmp =0;
int en_desordre =1;
while(en_desordre)
{
en_desordre = FALSE;
for(j =0 ; j < n-1 ; j++)
{
if(t[j] > t[j+1])
{
tmp = t[j+1];
t[j+1] = t[j];
t[j] = tmp;
en_desordre = TRUE;
}
}
}
}
// tri par sélection
void tri_par_selection(int*t, int n)
{
int i, min, j , tmp;
for(i =0 ; i < n -1 ; i++)
{
min = i;
for(j = i+1 ; j < n ; j++)
if(t[j] < t[min])
min = j;
if(min != i)
{
tmp = t[i];
t[i] = t[min];
t[min] = tmp;
}
}
}
// tri par insertion
void tri_insertion(int*t, int n)
{
int i, p,j;
int x;
for (i =1; i < n; i++)
{
x = t[i];
p = i-1;
while (t[p] > x && p-- >0) {}
p++;
for (j = i-1; j >= p; j--) {
t[j+1] = t[j];
}
t[p] = x;
}
}
// tri rapide
void echanger (int*t, int i, int j)
{int tmp;
tmp=t[i];
t[i]=t[j];
t[j]=tmp;
}
int partition(int*t, int deb, int fin)
{
int compt=deb;
int pivot=t[ deb] ;
int i;
for(i=deb+1;i<=fin;i++){
if(t[i]<pivot){
compt++;
echanger(t,compt,i);
}
}
echanger(t,compt,deb);
return(compt);
}
void tri_rapide_T (int*t, int debut,int fin)
{
if(debut<fin)
{
int pivot=partition( t,debut, fin) ;
tri_rapide_T(t,debut,pivot-1);
tri_rapide_T(t,pivot+1,fin);
}
}
void tri_rapide(int*t,int n)
{
tri_rapide_T(t,0,n-1);
}
int main(void)
{
int nb_entiers;
int*tab;
int i;
int num;
printf("Donner le nombre des entiers que vous voulez trier: ");
scanf("%d",&nb_entiers);
tab=(int *)malloc(nb_entiers*sizeof(int));
printf("\n");
for(i=0;i<nb_entiers;i++){
printf("Donner l'entier %d: ",i+1);
scanf("%d",&tab[i]);
}
printf("1. Le tri par fusion\n");
printf("2. Le tri en bulle\n");
printf("3. Le tri par selection\n");
printf("4. Le tri par insertion\n");
printf("5. Le tri rapide\n");
printf("entrer votre choix: \n");
int cas;
scanf("%d",&cas);
while(cas!=0){
// appliquer l'algorithme choisi
if(cas==1){ tri_fusion(tab,nb_entiers);
printf("\n tries! : ",144);
for(i=0;i<nb_entiers;i++) printf("%3d",tab[i]);
printf("\n\n");}
if(cas==2) {tri_en_bulle(tab,nb_entiers);
printf("\n tries! : ",144);
for(i=0;i<nb_entiers;i++) printf("%3d",tab[i]);
printf("\n\n");}
if(cas==3) {tri_par_selection(tab, nb_entiers);
printf("\n tries! : ",144);
for(i=0;i<nb_entiers;i++) printf("%3d",tab[i]);
printf("\n\n");}
if(cas==4) {tri_insertion(tab,nb_entiers);
printf("\n tries! : ",144);
for(i=0;i<nb_entiers;i++) printf("%3d",tab[i]);
printf("\n\n");}
if(cas==5) {tri_rapide(tab,nb_entiers);
printf("\n tries! : ",144);
for(i=0;i<nb_entiers;i++) printf("%3d",tab[i]);
printf("\n\n");}
cas=0;
printf("1. Le tri par fusion\n");
printf("2. Le tri en bulle\n");
printf("3. Le tri par selection\n");
printf("4. Le tri par insertion\n");
printf("5. Le tri rapide\n");
printf("entrer votre choix: \n");
int cas;
scanf("%d",&cas);
}
system("PAUSE");
return 0;
}
