#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Exercice 1

void tri_insertion(int tab[], int taille)
{
  int buff;
  for (int i = 1 ; i < taille ; i += 1)
  {
    int j = i;
    while (j > 0 && tab[j] < tab[j-1])
    {
      buff = tab[j];
      tab[j] = tab[j-1];
      tab[j-1] = buff;
      j -= 1;
    }
  }
}

int main1_1()
{
  int tab[] = { 3 , 7 , 4 , 1 , 5 , 2 , 6 };
  tri_insertion(tab, 7);
  for (int i = 0 ; i < 7 ; i += 1) printf("%d ", tab[i]);
  return 0;
}

void tri_selection(int tab[], int taille)
{
  int buff;
  for (int i = 0 ; i < taille-1 ; i += 1)
  {
    int posmin = i;
    for (int j = i+1 ; j < taille ; j += 1)
    {
      if (tab[j] < tab[posmin]) posmin = j;
    }
    if (posmin != i) // Vérification non nécessaire, mais parfois vérifier systématiquement pour affecter moins est moins cher qu'affecter systématiquement
    {
      buff = tab[posmin];
      tab[posmin] = tab[i];
      tab[i] = buff;
    }
  }
}

int main1_2()
{
  int tab[] = { 3 , 7 , 4 , 1 , 5 , 2 , 6 };
  tri_selection(tab, 7);
  for (int i = 0 ; i < 7 ; i += 1) printf("%d ", tab[i]);
  return 0;
}

// Exercice 2

void tri_cocktail(int tab[], int taille)
{
  int seuils[2] = { 0, taille-1 };
  bool trie = false;
  int cro = 1;
  int buff;
  while (!trie && seuils[0] < seuils[1])
  {
    trie = true;
    for (int i = seuils[(1-cro)/2] ; i != seuils[(cro+1)/2] ; i += cro)
    {
      if (tab[i]*cro > tab[i+cro]*cro)
      {
        buff = tab[i];
        tab[i] = tab[i+cro];
        tab[i+cro] = buff;
        trie = false;
      }
    }
    seuils[(cro+1)/2] -= cro;
    cro *= -1;
  }
}

int main2()
{
  int tab[] = { 3 , 7 , 4 , 1 , 5 , 2 , 6 };
  tri_cocktail(tab, 7);
  for (int i = 0 ; i < 7 ; i += 1) printf("%d ", tab[i]);
  return 0;
}

// Exercice 3 exclusivement en OCaml

// Exercice 4

void tri_denombrement(int tab[], int taille, int k)
{
  int *compteurs = malloc((k+1) * sizeof(int));
  for (int i = 0 ; i <= k ; i += 1) compteurs[i] = 0;
  for (int i = 0 ; i < taille ; i += 1) compteurs[tab[i]] += 1;
  int ind = 0;
  for (int i = 0 ; i <= k ; i += 1)
  {
    for (int j = 0 ; j < compteurs[i] ; j += 1)
    {
      tab[ind] = i;
      ind += 1;
    }
  }
  free(compteurs);
}

int main4()
{
  int tab[] = { 3 , 1 , 2 , 0 , 1 , 2 , 1 , 0 , 2 , 2 , 1 , 3 , 3 , 1 , 2 , 3};
  tri_denombrement(tab, 16, 3);
  for (int i = 0 ; i < 16 ; i += 1) printf("%d ", tab[i]);
  return 0;
}

// Fonction main

int main()
{
  int zero = main1_1();
  exit(zero);
}