/**************************************************************************
-ce programme est une implementation du tri Insertion
-En effet, le pricipe de ce tri est qu'on insere a la partie deja triee du tableau
une nouvelle valleur  prise dans la partie non triee a la bonne place dans le tableau
***************************************************************************/
#include <iostream>

using namespace std;
/*Differents Prototypes de Fonction */
void Insere(int *, int , int );
void Tri_Insertion(int *, int , int );
void Tri_Insertion_R(int *, int , int );
void Afficher(int *, int, int );



int main()
{
    int Tab[] = {10,6,30,40,7,2};

    cout << "\nValeur du tableau nom trie : \n";
    Afficher(Tab, 0, 6);
	//Appel de la fonction du tri insertion iteratif
    Tri_Insertion(Tab, 0, 6);
	cout << "\nValeur du tableau trie : \n";
	//Appel de la fonction du tri insertion recurssif
    Tri_Insertion_R(Tab, 0, 6);
    cout << "\nValeur du tableau trie : \n";

    Afficher(Tab, 0, 6);
    return 0;
}

//Fonction Insere qui insere une valeur à a onne place
void Insere(int *Tab, int G, int i)
{
    int j = i-1, temp = Tab[i];
    while(j >= G && Tab[j] > temp)
    {
        Tab[j+1] = Tab[j]; //Copie d'une case dans la case suivante
        j--;
        }
    Tab[j + 1] = temp;
    }

//La fonction du tri insertion Iteratif
void Tri_Insertion(int *Tab, int G, int D)
{
    int i;
    for(i= G+1; i <= D; i++)
    Insere(Tab, G, i);
    }

//La fonction du tri insertion recurssif
void Tri_Insertion_R(int *Tab, int G, int D)
{

    if(D-G >= 1)
    {
    Tri_Insertion_R(Tab, G, D-1);

    Insere(Tab, G, D);
    }
}
//Fonction d'affichage des elements du tableau
void Afficher(int *Tab, int G, int D)
{
    int i;

    for(i= G; i< D; i++)
    cout << Tab[i] <<" | ";
    cout<< endl;
    }