/*

dnob700 AT secionpc DOT info

*/
#include <iostream>
using namespace std;
/*

L'ensemble de ce tutorial demande déjà une réelle connaissance du C++, c'est à
dire de ce qu'est une classe, de savoir utiliser des pointeurs, etc.

Ce tutorial va présenter diverse notion d'algorithmique répartie sur plusieurs lessons. Chaque notion est introduite autour d'un ou deux algorithmes déclineés en plusieurs versions pour donner immédiatement des exemples pratiques du cours.

Le but de ce premier chapitre est juste de présenter deux algorithmes de tri
et le vocabulaire qui va autour pour introduire des notions d'algorithmiques.
Le chapitre 2 montrera l'importance de la complexité d'un algorithme.
Puis nous entamerons les problème d'algorithmique proprement dit.

Introduction mathématique :
  Un algorithme est un ensemble d'opérations qui permet de réaliser une tâche bien définie en un nombre d'opération fini.
  Par exemple trier un paquet de cartes peut être une tache à faire réaliser par un algorithme, on peut imaginer la méthode qui consiste à prendre une carte puis à mettre chacune des cartes suivantes à leur place petit à petit dans le paquet que l'on forme ainsi (c'est ce qu'on appelle le tri par insertion) on voit qu'il faudra prendre au maximum 52 carte pour qu'elles soient toutes triées.
  Par contre la méthode qui consiste à jeter les cartes par terre, à les ramasser, et à recommencer jusqu'à ce que le jeu soit bien ordonné, n'est pas un algorithme car il ne se fait pas en un nombre d'opération fini.

Notre premier exemple sera donc le tri.
pour celà nous allons étudier deux algorithme, un basic, le tri à bulle, et un avancé, le tri-rapide.

Tout les tris que nous allons écrire seront écrit pour trier des int, mais ils pourraient fonctionner avec n'importe quel type sur lesquels on peut définir un ordre totale (c'est a dire que pour deux éléments quelconques on ait toujours soit a<b soit b<a (ou les deux mais alors a=b)

*/

//première méthode, tri à bulle
void tri_a_bulle(int *tableau,int nb_elem)
{
  bool fini=true;
  int temp;
  int i;
  do
  {
    fini=true;
    for (i=1;i<nb_elem;i++)
    {
      if (tableau[i-1]>tableau[i])
      {
        fini=false;
        temp=tableau[i-1];
        tableau[i-1]=tableau[i];
        tableau[i]=temp;
      }
    }
  }while(!fini);
}

// Nous allons la tester tout de suite, pour celà on écrit une fonction d'affichage
void affiche_list(int *tableau,int nb_elem)
{
  int i;
  for (i=0;i<nb_elem;i++)
    cout << tableau[i] << " ";
  cout << endl;
}


//et on teste tout ça :
void main()
{
  int n=0;
  int tableau[50];
  cout << "entrer des nombres, 0 pour finir." << endl;
  do
  {
    cin >> tableau[n++]; //On incrémente n après avoir enregistré le nombre
  }while (tableau[n-1]!=0&&n<50);
  tri_a_bulle(tableau,n-1);
  affiche_list(tableau,n-1);
  cin.get();cin.get();
}

/*

  Mais comment marche ce tri ? c'est très simple, il trie par ordre croissant,
donc il regarde si deux éléments successif sont dans le bon ordre (petit devant)
et si non il les inverse. Et il parcourt toute la liste comme ça, puis recommence
jusqu'à faire un parcourt complet sans faire aucun échange (c'est à ça que sert
la variable fini) alors il s'arrète.
  Mais comment sait-on qu'il s'arrète me direz vous ? et bien c'est simple, la
boucle principale ne peut pas faire plus de nb_elem boucle car à ce moment là,
même l'élément le plus mal placé est retourné à sa place.

Mais tout ça, c'est facile, le tri à bulle est simple mais très inefficace.
Pour n éléments, il faut au pire n^2 opérations de bases (je vais y revenir) :
les n du for multiplié par les n du do...while. On dit que la complexité est en
O(n^2) ce qui veut dire que si au pire pour n éléments la méthode prend un temps
T alors pour 2*n éléments on aura besoin d'un temps 4*T etc. (pour ceux qui ont
fait des math, O(n^2) c'est un grand O comme pour les suites ou les fonctions).

J'ai parlé d'opérations de bases tout à l'heure. Il s'agit de la plus petite
opération que va effectuer l'algorithme. parfois on compte en nombre d'opération
pour le processeur, mais ici ça serait trop compliqué, donc on comptera en
nombre de permutation effectuée. En fait, il est plus pertinant de regarder la
qualité d'un algorithme à son nombre d'opération plutot qu'à son temps d'exécution
qui est quelque chose de bcp plus difficile à calculer.

Il y a une variante du tri a bulle qui est le tri par selection.
je donne ici une procédure le mettant en oeuvre, juste pour information :
*/
void tri_par_selection(int *tableau,int nb_elem)
{
  int i,j,t,temp;
  for (i=0;i<nb_elem-2;i++)
  {
    t=i;
    for (j=i+1;j<nb_elem;j++)
      if (tableau[j]<tableau[t])
        t=j;
    temp=tableau[i];
    tableau[i]=tableau[t];
    tableau[t]=temp;
  }
}
/* Ce tri fait autant de teste de que le à bulle et est aussi en O(n^2) mais il fait moins
d'interversion de valeurs, donc on peut gagner un peu de temps.

Maintenant passons au chose sérieuse, et voici l'algorithme de tri rapide.

*/

//Le tri rapide
void tri_rapide(int *tableau, int nb_elem)
{
  int *table=new int[nb_elem];
  int d,f,i;
  d=0;
  f=nb_elem-1;
  i=0;
  int centre=tableau[i++];

  //On classe les éléments selon qu'ils sont plsu grand ou plus petit que tableau[0]
  for (;i<nb_elem;i++)
  {
    if (tableau[i]<centre)
      table[d++]=tableau[i];
    else
      table[f--]=tableau[i];
  }
  table[d]=centre;

  //On recopie dans le bon tableau celui qui est trié (quel gachis).
  for (i=0;i<nb_elem;i++)
    tableau[i]=table[i];

  delete[] table;

  //Si nécessaire on re-tri ce qui reste de la liste.
  if (d>1)
    tri_rapide(tableau,d);
  if (f<nb_elem-3)
    tri_rapide(&tableau[f+1],nb_elem-f-1);
}

/*

  Tout d'abord, je tiens à vous avouer que cette algorithme est très mauvais car
il gère très mal la mémoire, mais c'est pour la démonstration (je vous ais mis
une bonne version à la fin du fichier).

Ce tri, consiste d'abord à sélectionner un éléments au hasard dans la liste à
trier (ici on prend au hasard le premier (!) ce qui n'est pas toujours le plus
judicieux) puis à classer les éléments selon qu'ils sont plus gros ou plus petit
que l'élément que l'on a choisi au début. Quand c'est fait, on replace au milieu
cet élément qui est à sa bonne place, puis on trie de la même manière la moitié
à gauche du dernier élément et celle à droite.
On remarque que dans le pire des cas la complexité de l'algorithme est en O(n^2)
mais si les découpage en deux moitié sont toujours à peu près égale alors la
complexité est en O(n*log(n)) ce qui est beaucoup mieux. Malheureusement,
rechercher l'élément médian, c'est à dire celui qui couperait la liste en deux
partie de même taille est très complexe (en terme de temps de calcul) et donc
relève du gaspilage, lorsque l'on ne sait rien de la liste.

Mais comme pour tout les algorithme, la méthode peut être grandement accélérée si
l'on a des informations sur la liste initiale.

Pour tester l'algorithme, mettez la première fonction main en commentaire et décommentez celle qui suit.
*/

//et on teste tout ça :
/*
void main()
{
  int n=0;
  int tableau[50];
  cout << "entrer des nombres, 0 pour finir." << endl;
  do
  {
    cin >> tableau[n++];
  }while (tableau[n-1]!=0&&n<50);
  tri_rapide(tableau,n-1);
  affiche_list(tableau,n-1);
  cin.get();cin.get();
}
*/

/*

Chose promise chose due, voici un meilleur algorithme de tri rapide, même s'il
n'est pas parfait non plus.
Chacun des ces algorithmes et particulièrement celui qui suit, représente ma vision personnelle de la solution (j'ai étonament été dans l'impossibilité de trouver un programme en C montrant une implémentation du tri-rapide). Cette solution me semble acceptable du fait qu'elle miniminise les échange de valeurs ainsi que l'utilisation de la mémoire (ce qui n'était pas le cas de l'autre algorithme). 
*/



void tri_plus_rapide(int *t,int n)
{
  int *d=&t[1];
  int *f=&t[n-1];
  int c=t[n/2];
  t[n/2]=*t;
  int v=*t;
  int tt;

  while (d<f)
    if (v<=c)
      if (v==*d) v=*(++d);
      else
        if (*d<=c) d++;
        else {
          tt=*d;
          *d=v;
          v=tt;
          d++; }
    else
      if (v==*f) v=*(--f);
      else
        if (*f>c) f--;
        else {
          tt=*f;
          *f=v;
          v=tt;
          f--; }

  if (v<=c) {
    *t=v;
    *d=c;
    f++; }
  else {
    d--;
    *t=*d;
    *d=c;
    *f=v; }

  if (d-t>1) tri_plus_rapide(t,(int)(d-t));
  if (n-(f-t)>1) tri_plus_rapide(f,(int)(n-(f-t)));
  //Les deux dernières lignes ne sont pas très rigoureuses car la conversion en int de mes différence de pointeurs pourrait échouer sur certain système (en théorie, mais en fait je crois que ça doit marcher tout le temps).
}