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


struct list_t{
  int value; 			/* valeur stockee dans ce noeud de la liste */
  struct list_t* next;		/* pointeur vers le prochain noeud de la liste */
};

/* cree un nouveau noeud contenant value et l'insere dans la liste */
void list_add(struct list_t **list, int value) {
  struct list_t* new_node = malloc(sizeof(struct list_t));
  new_node->value = value;
  new_node->next = *list;
  *list = new_node;
}

/* affiche les noeuds d'une liste */
void print_list(struct list_t* list) {
  if(!list) {
    printf("NULL\n");
    return ;
  }
  printf("%d -> ", list->value);
  print_list(list->next);
}

/* trie une liste */
void sort_list(struct list_t** list) {
  if(! (*list)) {
    /* la liste est vide */
    return ;
  }

  struct list_t*min_node = *list;
  struct list_t** cur_node=&(*list)->next;
  /* on trouve le min */
  while(*cur_node) {
    if((*cur_node)->value < (*list)->value) {
      /* on a trouve un min. On insere cur_node */
      min_node = *cur_node;
      /* on retire cur_node de la liste */
      (*cur_node) = (*cur_node)->next;
      min_node->next = *list;
      *list = min_node;
    } else {
      cur_node = &(*cur_node)->next;
    }
  }
  /* trie le reste de la liste */
  sort_list(&min_node->next);
}

/* libere les noeuds d'une liste */
void free_list(struct list_t** list) {
  if(! (*list)) {
    /* la liste est vide */
    return;
  }
  free_list(&(*list)->next);
  free(*list);
  *list = NULL;
}

int main(int argc, char**argv) {
  struct list_t *list = NULL;
  int nitem = 30;
  int i;
  srand(time(NULL));
  /* creation de la liste: on tire au sort n valeurs qu'on insère */
  for(i=0; i<nitem; i++) {
    int value = rand()%(nitem*10);
    list_add(&list, value);
  }

  /* on affiche la liste */
  print_list(list);

  /* On trie la liste et on affiche le resultat */
  printf("on trie la liste\n");
  sort_list(&list);
  printf("Résultat du tri: \n");
  print_list(list);

  /* libere les blocs alloues */
  free_list(&list);
  return EXIT_SUCCESS;
}