#include <stdio.
h>
#include<time.h>
// Fonction pour afficher un tableau d'entiers
void afficherTableau(int arr[], int a)
{
for (int i = 0; i < a; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// Tri par insertion
void triInsertion(int arr[], int a)
{
clock_t debut,fin;
double temps;
debut=clock();
for (int i = 1; i < a; i++) {
int cle = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > cle) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = cle;
}
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f :/n", temps);
}
// Tri à bulles
void triBulles(int arr[], int a)
{
clock_t debut,fin;
double temps;
debut=clock();
for (int i = 0; i < a - 1; i++) {
for (int j = 0; j < a - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f :/n", temps);
// Tri fusion
void fusion(int arr[], int gauche, int milieu, int droite)
{
int i, j, k;
int n1 = milieu - gauche + 1;
int n2 = droite - milieu;
int L[n1], R[n2];
clock_t debut,fin;
double temps;
debut=clock();
for (i = 0; i < n1; i++) {
L[i] = arr[gauche + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[milieu + 1 + j];
}
i = 0;
j = 0;
k = gauche;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f :/n", temps);
void triFusion(int arr[], int gauche, int droite)
{
clock_t debut,fin;
double temps;
debut=clock();
if (gauche < droite) {
int milieu = gauche + (droite - gauche) / 2;
triFusion(arr, gauche, milieu);
triFusion(arr, milieu + 1, droite);
fusion(arr, gauche, milieu, droite);
}
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f s :/n", temps);
// Tri rapide
int partition(int arr[], int bas, int haut) {
int pivot = arr[haut];
int i = (bas - 1);
for (int j = bas; j <= haut - 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[haut];
arr[haut] = temp;
return (i + 1);
}
void triRapide(int arr[], int bas, int haut)
{
clock_t debut,fin;
double temps;
debut=clock();
if (bas < haut) {
int pivot = partition(arr, bas, haut);
triRapide(arr, bas, pivot - 1);
triRapide(arr, pivot + 1, haut);
}
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f :/n", temps);
// Tri par dénombrement
void triDenombrement(int arr[], int a)
{
int max = arr[0];
clock_t debut,fin;
double temps;
debut=clock();
for (int i = 1; i < a; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int *comptage = (int *)calloc(max + 1, sizeof(int));
int *resultat = (int *)malloc(a * sizeof(int));
for (int i = 0; i < a; i++) {
comptage[arr[i]]++;
}
for (int i = 1; i <= max; i++) {
comptage[i] += comptage[i - 1];
}
for (int i = a - 1; i >= 0; i--) {
resultat[comptage[arr[i]] - 1] = arr[i];
comptage[arr[i]]--;
}
for (int i = 0; i < a; i++) {
arr[i] = resultat[i];
}
free(comptage);
free(resultat);
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f :/n", temps);
// Radix Sort
int getMax(int arr[], int a)
{
int max = arr[0];
for (int i = 1; i < a; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
void triRadix(int arr[], int a)
{
int max = getMax(arr, a);
clock_t debut,fin;
double temps;
debut=clock();
for (int exp = 1; max / exp > 0; exp *= 10) {
int resultat[a];
int comptage[10] = {0};
for (int i = 0; i < a; i++) {
comptage[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
comptage[i] += comptage[i - 1];
}
for (int i = a - 1; i >= 0; i--) {
resultat[comptage[(arr[i] / exp) % 10] - 1] = arr[i];
comptage[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < a; i++) {
arr[i] = resultat[i];
}
}
fin=clock();
temps = ((fin-debut)/CLOCKS_PER_SEC);
printf("le code a pris %f :\n", temps);
int main() {
int c,a,arr[100]={0} ;
int i,b=0;
do{
printf("entez le nombre de case :\n ");
scanf("%d",&a);
}while(a<=0);int taille = sizeof(arr) / sizeof(arr[0]);
;
do{
printf("1-remplir un tableau\n");
printf("2-Trie par insertion\n");
printf("3-Trie à bulles\n");
printf("4-Trie fusion\n");
printf("5-Trie rapide\n");
printf("6-Trie par dénombrement\n");
printf("7-Trie Radix\n");
printf("8-Quitter\n");
scanf("%d",&c);
switch(c)
{
case 1:
for(i=0;i<a;i++)
{
printf("entrez le nombre de la case %d : \n",i+1);
scanf("%d",&b);
arr[i]=b;
}
break;
case 2:
triInsertion(arr, a);
afficherTableau(arr, a);
break;
case 3:
triBulles(arr, a);
afficherTableau(arr, a);
break;
case 4:
triFusion(arr, 0, a - 1);
afficherTableau(arr, a);
break;
case 5:
triRapide(arr, 0, a - 1);
afficherTableau(arr, a);
break;
case 6:
triDenombrement(arr, a);
afficherTableau(arr, a);
break;
case 7:
triRadix(arr, a);
afficherTableau(arr, a);
break;
}
}while(c!=8);
return 0;
}
