ca sert a rien d'autre qu'a trier,
c'set pour comparer toutes les sortes de tris, et calculer le temps, faire des graphiques..
j'ai essayer de mettre des commentaires, et de le rendre plus lisibles, je c pas si je peux faire plus ...
tout les tris fonctionne mem avec taille, j'ai mis comme le prof a dis, c'est bizzar, ya que shell qui tri pas bien !
sinon laisse tomber, t'facon je crois que j'v abandonné l'informatique ca me saoule, g deja mon bts c pas mal ;-) lol
#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#define taille
int tab[taille];
/************************ programme principal ****************************/
int main()
{
/* déclarations */
int choix=0,cont;
cont=1;
while(cont==1){
/* affichage du menu */
printf("\n\n\t\t\t ****************\n");
printf("\t\t\t *MENU PRINCIPAL*\n");
printf("\t\t\t ****************\n\n\n\n");
printf("\t TAPEZ :\n\n\n\n");
printf("\t\t1\t Pour :\t Lancer le prog de tri a bulle\n\n");
printf("\t\t2\t Pour :\t Lancer le prog de tri par insertion\n\n");
printf("\t\t3\t Pour :\t Lancer le prog de tri par ext\n\n");
printf("\t\t4\t Pour :\t Lancer le prog de tri shell\n\n");
printf("\t\t5\t Pour :\t Lancer le prog de tri fusion\n\n");
printf("\t\t6\t Pour :\t Lancer le prog de tri rapide\n\n");
printf("\t\t7\t Pour :\t Quitter le programme\n\n\n");
printf("\t CHOIX : ");
scanf("%d",&choix);
/* menu */
switch(choix)
{
case 1 :
init(tab);
tri_bulle(tab);
affich(tab);
break;
case 2 :
init(tab);
tri_ins(tab);
affich(tab);
break;
case 3 :
init(tab);
tri_ext(tab);
affich(tab);
break;
case 4 :
init(tab);
tri_shell(tab);
affich(tab);
break;
case 5 :
init(tab);
tri_fusion(tab);
affich(tab);
break;
case 6 :
init(tab);
tri_rapide(tab);
affich(tab);
break;
default : cont=0; /* sortie du programme*/
}
}
}
/****************************initialisation du tableau******************/
int init(int tab[]) {
int nb,i; /* déclarations */
srand(time(NULL)); /* Initialisation du générateur aléatoire avec la fontion time */
printf("\n\n Nombre de valeurs a trier (du tableau) : ");
scanf("%d", &nb); /* Demande le nombre d'éléments à trier */
printf("\n");
for(i=0;i<nb;i++) /* Remplissage du tableau aléatoirement */
tab[i]=rand()%1000;
printf("Les valeurs avant le tri : "); /* affichage du tableau */
for(i=0; i<nb;i++)
printf("\n%d ",tab[i]);
}
/****************************affichage du tableau trié******************/
int affich(int tab[]) {
int nb,i; /* déclarations */
printf("\n\nLes valeurs apres le tri :"); /* affichage du tableau */
for(i=0; i<nb;i++)
printf("\n%d ",tab[i]);
system("PAUSE");
}
/****************************tri bulle*********************************/
int tri_bulle(int tab[])
{
int der,i,j,permut; /* Déclarations */
for (i=0; i<der; i++) /* tri */
for (j=der-1; j>i; j--) /* on compare un à un */
if (tab[j-1] > tab[j]) {
permut = tab[j-1]; /* permutation */
tab[j-1] = tab[j];
tab[j] = permut;
}
}
/****************************tri par insertion ****************************/
int tri_ins(int tab[])
{
int der,i,j,temp; /* Déclarations */
/* tri */
for (i=0; i<der; i++){
temp=tab[i];
j=i;
while (tab[j-1] > temp) { /*on decale les éléments */
tab[j] = tab[j-1];
j--;
}
tab[j]=temp;
}
}
/****************************tri par extraction ****************************/
int tri_ext(int tab[])
{
int der,i,j,permut,temp; /* déclarations */
for (i=0; i<der; i++){ /* tri */
temp=i;
for(j=i+1;j<der;j++)
if (tab[j]<tab[temp]) /* on compare les élément du tableau */
temp = j;
permut = tab[temp]; /* permutation */
tab[temp] = tab[i];
tab[i] = permut;
}
}
/****************************tri shell **********************************/
int tri_shell(int tab[])
{
int i,j,pas,temp,n,nb; /* déclarations */
n=nb;
for ( pas=1 ; pas<=n/9; pas=3*pas+1); /* tri */
for ( ; pas>0 ; pas /=3)
for ( i=pas ; i<n ; i++ ){
temp = tab[i] ;
j = i ;
while (j>pas && tab[j-pas]>temp) {
tab[j] = tab[j-pas] ;
j -= pas ;
}
tab[j] = temp ;
}
}
/****************************tri fusion ****************************/
void interclasse(int tab[], int g, int mid, int d)
{
int tab_aux[d]; /* Tableau auxiliaire */
int i=g, j=mid+1 , ga=g;
/* Fusion dans le tableau auxiliaire */
while(i<=mid && j<=d)
if (tab[i]<tab[j])
tab_aux[ga++]=tab[i++];
else
tab_aux[ga++]=tab[j++];
if (i>mid)
while(j<=d)
tab_aux[ga++]=tab[j++];
else
while(i<=mid)
tab_aux[ga++]=tab[i++];
/* Recopie du tableau auxiliaire dans tab */
for(i=g;i<=d;i++)
tab[i]=tab_aux[i];
}
void fusion(int T[], int g, int d) {
int i,m;
if (g < d) {
m = (g+d)/2;
fusion(T, g, m); /* m tjs < b */
fusion(T, m+1, d); /* m+1 tjs > a donc pas de bouclage possible */
interclasse(T, g, m, d);}
}
int tri_fusion(int tab[]) {
int nb;
fusion(tab, 0, nb-1); /* appel de la fonction fusion */
}
/************************ tri rapide ****************************/
/* réordonne le tableau et rend l'indice de séparation */
int permutation(int T[], int g, int d) {
int i, j, pivot, bi = g, bs = d, r, TI[d]; /* déclarations */
pivot = T[g]; /* choix du pivot*/
for(i=g;i <= d;i++) {
if (T[i] < pivot) {
TI[bi] = T[i];
bi++; }
if (T[i] > pivot) {
TI[bs] = T[i];
bs--; }
}
for(i=bi;i<=bs;i++) /* On place le ou les pivots */
TI[i] = pivot;
for(i=g;i <= d;i++) { /* recopie de TI */
T[i] = TI[i];
if (T[i] == pivot)
r = i;
}
return r;
}
void rapide(int T[], int g, int d) {
int separe; /* déclarations */
if (g < d) {
separe = permutation(T, g, d); /* apel de la fonction permutation */
rapide(T, g, separe-1); /* apel de la fonction rapide */
rapide(T, separe+1, d); }
}
int tri_rapide(int tab[]) {
int nb; /* déclarations */
rapide(tab, 0, nb-1); /* appel de la fonction rapide */
}
/* FIN*/