Soit un tableau de valeur non triées. Algorithme :

class TriparInsertion
{
     int tab[ ]; //tableau de valeur à trier
     void trierParInsertion( )
     {
          for(int i=1; i=0) && (tab[j+1] < tab[j]); j--)
               {     //inversion 
                    int temp = tab[j+1];
                    tab[j+1] = tab[j];
                    tab[j] = temp;
               }
          }
     }
}

Exemple :

7 2 4 6 3 9 8 5 
2 7 4 6 3 9 8 5 
2 4 7 6 3 9 8 5
2 4 6 7 3 9 8 5
2 4 6 3 7 9 8 5 
2 4 3 6 7 9 8 5
2 3 4 6 7 9 8 5 
2 3 4 6 7 8 9 5 
2 3 4 6 7 8 5 9
2 3 4 6 7 5 8 9
2 3 4 6 5 7 8 9 
2 3 4 5 6 7 8 9

Dans le meilleur des cas : O(n) pour un tableau déjà trié. Dans le pire des cas : O(n²) pour un tableau triè dans l'ordre inverse. L'algorithme est très simple à écrire mais de mauvaise complexité dans certain cas. Réservé aux cas des petits tableaux (n < 20) car le facteur multiplicatif (qui est supprimé dans la notion O(…) est petit, alors que les algorithmes, en théorie meilleurs, ont des gros facteurs multiplicatifs : 100n log(n)

Chaque noeud n'a qu'un seul père. Un noeud a 1 ou 0 père. Une feuille est un noeud sans fils. La racine est un noeud unique sans père. La hauteur d'un arbre est la distance entre la racine et la feuille la plus éloignée. Les arbres binaires : Tout noeud a 0, 1 ou 2 fils. Les arbres binaires équilibrés : Il s'agit d'un arbre binaire où chaque noeud a 2 fils obligatoirement, sauf ceux du dernier niveau. Tas : Il s'agit d'un arbre binaire équilibré, contenant des valeurs (1 par noeud) telles que tout noeud contient une valeur plus grande ou égale à son fils.

2 phases : construction du tas puis destruction du tas. Construction du tas On ajoute les valeurs une par une. On met chaque valeur le plus en bas à gauche du tas On la compare à son père. Si elle est plus grande on fait l'échange et on recommence.

Exemple :

7 2 4 6 3 9 8 5
     on ajoute 7
               7
     on ajoute 2
               7
            2
     on ajoute 4
               7    
            2     4
     on ajoute 6
               7	      				       
            2    4   					  
         6					         
etc ...
        9
    6      8
  5  3  4  7
2                        ............ au final !