#include <stdio.h>
#include <stdlib.h>	// pour les fonctions rand() et srand()
#include <time.h>	// pour la fonction time()
#include <stdbool.h> //nécessite la compilation avec l'option -std=c99

#define N 10000

/* trie le tableau d'entier en utilisant l'algorithme du tri à bulles */
void tri_bulles(int *tab, size_t taille);


/* trie le tableau d'entier en utilisant l'algorithme du tri à bulles optimisé */
void tri_bulles_optimise(int *tab, size_t taille);


/* trie le tableau d'entier en utilisant l'algorithme du tri par insertion */
void tri_insertion(int *tab, size_t taille);


/* trie le tableau d'entier en utilisant l'algorithme du tri par sélection */
void tri_selection(int *tab, size_t taille);


/* fonction qui permet de tester si un tableau d’entiers est trié*/ 
bool est_trie(const int *tab, size_t taille);


/* fonction qui affecte, dans les éléments d'un tableau d'entiers, 
des valeurs pseudo-aléatoires comprises dans l'intervalle [0; val_max]*/
void affecte_alea(int *tab, size_t taille, int val_max);


/* fonction qui affiche sur une ligne les éléments d'un tableau d'entiers */
void affiche(const int *tab, size_t taille);


int main()
{
  	//srand (time(NULL));

	int t[N];

	printf("\nTri a bulles\n");
	affecte_alea(t, N, N);
	printf("1. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	tri_bulles(t, N);
	printf("2. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	affiche(t, 10);			// affiche les 10 premiers éléments du tableau
	affiche(t+N-10, 10);	// affiche les 10 derniers éléments du tableau

	srand(1);  	// afin de re-initialiser la graine du générateur pseudo-aléatoire à sa valeur par défaut
				// et que la fonction affecte_alea() affecte les mêmes valeurs dans le tableau que lors de son appel précédant
	printf("\nTri a bulles optimise\n");
	affecte_alea(t, N, N);
	printf("1. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	tri_bulles_optimise(t, N);
	printf("2. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	affiche(t, 10);
    affiche(t+N-10, 10);

	srand(1);
	printf("\nTri par selection\n");
	affecte_alea(t, N, N);
	printf("1. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	tri_selection(t, N);
	printf("2. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	affiche(t, 10);
	affiche(t+N-10, 10);

	srand(1);
	printf("\nTri par insertion\n");
	affecte_alea(t, N, N);
	printf("1. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	tri_insertion(t, N);
	printf("2. le tableau %s\n", est_trie(t, N)? "est trie" : "n est pas trie");
	affiche(t, 10);
	affiche(t+N-10, 10);


	return 0;
}



/* trie le tableau d'entier en utilisant l'algorithme du tri à bulles */
void tri_bulles(int *tab, size_t taille)
{
    int temp;
    while (taille >= 2)
    {
       	for(size_t i=0; i <= taille -2 ; ++i )
        {
			if (tab[i] > tab[i+1])
			{
				temp = tab[i];
				tab[i] = tab[i+1];
				tab[i+1] = temp;
			}
        }
		--taille;
    }
}

/* trie le tableau d'entier en utilisant l'algorithme du tri à bulles optimisé */
void tri_bulles_optimise(int *tab, size_t taille)
{
    int temp;
	bool permut = true;
    while (permut && taille >= 2)
    {
     	permut = false;
       	for(size_t i=0; i <= taille -2 ; ++i )
        {
			if (tab[i] > tab[i+1])
			{
				temp = tab[i];
				tab[i] = tab[i+1];
				tab[i+1] = temp;
				permut = true;
			}
        }
		--taille;
    }
}

/* trie le tableau d'entier en utilisant l'algorithme du tri par insertion */
void tri_insertion(int *tab, size_t taille)
{
	for (size_t j=1; j< taille; ++j)
    {
		// j est l'indice de l'élément à insérer
		int x = tab[j];
		int i = j-1;
		// x doit être inséré dans le tableau ordonné 0..j-1
		// rq : on ne peut pas utiliser le type size_t pour la variable i
		// car lorsqu'il faut insérer l'élément à l'indice 0, on sort de la boucle ci-dessous avec i = -1
		while (i>=0 && tab[i]>x)
		{
			tab[i+1] = tab[i];
			--i;
		}
		tab[i+1] = x;
    }
}

/* trie le tableau d'entier en utilisant l'algorithme du tri par sélection */
void tri_selection(int *tab, size_t taille)
{
	int  temp;
	size_t ind_min;
    if (taille <= 1)
    {
        // >>>>>>>>>>>> FIN DE LA FONCTION >>>>>>>>>>>>>>
        return;
    }
	// Sans le test ci-dessus, pb lorsqu'on appelle la fonction avec taille égal à 0.
	// En effet, taille - 1 vaut alors -1, et i est de type size_t (entier non signé).
	// Or, il ne faut jamais comparé un entier non signé avec un entier signé
	for (size_t i = 0 ; i < taille-1 ; ++i)
	{
		//on recherche la position de la plus petite valeur dans le tableau non encore triee
		ind_min = i;
      	for (size_t j = i + 1 ; j < taille ; ++j)
		{
       		if (tab[j] < tab[ind_min])
			{
				ind_min = j ;
			}
		}
		temp = tab[i];
		tab[i] = tab[ind_min];
		tab[ind_min] = temp;
	}
}

/* fonction qui permet de tester si un tableau d’entiers est trié*/ 
bool est_trie(const int *tab, size_t taille)
{
	bool res = true;
	size_t i = 0;
	if (taille <= 1)
    {
        // >>>>>>>>>>>> FIN DE LA FONCTION >>>>>>>>>>>>>>
        return true;
    }
	while (res && i < taille -1)
	{
		res = tab[i] <= tab[i + 1];
		++i;
	}
	return res;
}

/* fonction qui affecte, dans les éléments d'un tableau d'entiers, 
des valeurs pseudo-aléatoires comprises dans l'intervalle [0; val_max]*/
void affecte_alea(int *tab, size_t taille, int val_max)
{
	for(size_t i = 0; i < taille ; ++i)
	{
		tab[i] = rand() % (val_max +1);
	}
}
/* fonction qui affiche sur une ligne les éléments d'un tableau d'entiers */
void affiche(const int *tab, size_t taille)
{
	for (size_t i = 0; i < taille ; ++i)
	{
		printf("%d ", tab[i]);
	}
	printf("\n");
}