Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par insertion

Ada

type FloatArray is array(Natural range<>) of Float;
type Tab is access FloatArray;

procedure tri_insertion(t : in out Tab) is
    j : Natural;
    elementInsere : Float;
begin
    for i in t'Range loop
        elementInsere := t(i);
        
        j := i;
        while( j > t'First and then t(j - 1) > elementInsere ) loop
            t(j) := t(j - 1);
            j := j - 1;
        end loop;
        
        t(j) := elementInsere;
        
    end loop;
end tri_insertion;

C

Une mise en œuvre simple du tri par insertion sur un tableau de nombres flottants :

void tri_insertion(double* t, int n)
{
    int i, j;
    double elementInsere;

    for (i = 1; i < n; i++) {
        /* Stockage de la valeur en i */
        elementInsere = t[i];
        /* Décale les éléments situés avant t[i] vers la droite
           jusqu'à trouver la position d'insertion */
        for (j = i; j > 0 && t[j - 1] > elementInsere; j--) {
            t[j] = t[j - 1];
        }
        /* Insertion de la valeur stockée à la place vacante */
        t[j] = elementInsere;
    }
}

Objective-C

Une mise en œuvre simple du tri par insertion sur un tableau de nombres :

int j, i;
for (j = 1; j < sortedArray.count; j++)
{
    id myKey = [sortedArray objectAtIndex:j];
    i = j - 1;

    while (i >= 0 && [sortedArray objectAtIndex:i] < myKey)
    {
            [sortedArray replaceObjectAtIndex:i + 1 withObject:[sortedArray objectAtIndex:i]];
            i--;
    }

    [sortedArray replaceObjectAtIndex:i + 1 withObject:myKey];
}

Caml

Tri par insertion en utilisant des vecteurs (en ordre décroissant).

let tri_ins t =
  let n = vect_length t in
  let s = copy_vect t in (* permet de ne pas modifier le vecteur passé en argument *)
    for k = 1 to (n - 1) do
      let  x = t.(k) and j = ref( k - 1) in
        while ( !j >= 0 ) & ( x > s.(!j) ) do 
                           s.(!j + 1) <- s.(!j);
                           j:= !j - 1;
        done;                   
        s.( !j + 1 ) <- x;
    done;
  s;;

Tri par insertion récursif en utilisant des listes.

 let rec insere elem = function
     [] -> [elem]
   | tete::queue ->
       if elem <= tete
       then elem::tete::queue            (* on a trouvé la place de l'élément *)
       else tete :: (insere elem queue)  (* on continue à chercher dans la queue de la liste *)
 
 let rec tri_insertion = function
     [] -> []
   | tete::queue -> insere tete (tri_insertion queue)

On remarque que les listes sont des structures de données plus simples à trier par insertion que les tableaux, parce qu'il n'y a pas besoin de "décaler les éléments".

Haskell

Tri par insertion par ordre croissant en Haskell :

insTri :: Ord a => [a] -> [a]
insTri [] = []
insTri (x:xs) = inserer x (insTri xs)
  where inserer x [] = [x]
        inserer x (y:ys) | (x<=y)    = x:y:ys
                         | otherwise = y:(inserer x ys)

Java

Tri par insertion en ordre croissant en utilisant le langage Java (JDK avant la version 5.0)

public static void triParInsertion(int [] tab, int tailleLogique)
{
    for (int i = 1; i < tailleLogique ; i++)
    {    
        int element = tab[i];
        int cpt = i - 1;
        while (cpt >= 0 && tab[cpt] > element)
        {
           tab[cpt + 1] = tab[cpt];
           cpt--;
        }
        tab[cpt + 1] = element;
    }
}

JavaScript

T est un tableau de nombres et n est un entier tel que l'on veuille trier T[0..n-1].

function executer_tri_par_insertion (T, n) {
    if (T.length < 2) return T;
    var i, j, element_a_inserer;
    for (i = 1; i < n; i++) {
        element_a_inserer = T[i];
        j = i;
        while (j > 0 && element_a_inserer < T[j-1]) {
            T[j] = T[j-1];
            j--;
        }
        T[j] = element_a_inserer;
    }
    return T;
}

PHP

Tri par insertion avec le langage PHP.

function Tri_insrt($liste, $taille )
{
    for($i = 0; $i < $taille; $i++)
    {
        $element_a_inserer = $liste[$i];
        for($j = 0; $j < $i; $j++)
        {
            $element_courant = $liste[$j];
            if ($element_a_inserer < $element_courant)
            {
                $liste[$j] = $element_a_inserer;
                $element_a_inserer = $element_courant;
            }  
        }
        $liste[$i] = $element_a_inserer;
    }
}

Pascal

function position (t:tab ; i : integer ): integer ; 
var 
   j : integer ; 
Begin 
 j:=0 ; 
  repeat 
   j:=j+1 ; 
  until t[j] >= t[i] ; 
 position:=j ; 
End; 
 
procedure tri(var t : tab ; n:integer ); 
var 
int,i,j,p : integer ; 
Begin 
 for i:=2 to n do 
  begin 
   p:=position(t,i); 
    if p <> i then 
     begin 
      int:=t[i] ; 
       for j :=i-1 downto p do 
        begin 
         t[j+1]:=t[j] ; 
        end; 
      t[p]:=int ; 
     end; 
  end;  
End;

Autre Méthode

procedure Tri_Insertion(n : integer; var t : tab);
var i, j, k : integer;
begin
	for i:=2 to n do
	begin
		k := t[i];
		
		{ Décale tous les éléments jusqu'à trouver le point d'insertion }
		j:=i - 1;
		while (j >= 1) and (t[j] > k) do 
		begin
			t[j + 1] :=  t[j];
			j := j - 1;
		end;
		
		t[j + 1] := k;
	end;
end;

Python

Tri par insertion avec le langage Python.

def insertionSort(array):
    for j in range(1, len(array)):
        i = j - 1
        tmp = array[j]
        while i > -1 and array[i] > tmp:
            array[i+1] = array[i]
            i -= 1
        array[i+1] = tmp

En récursif :

def insertion(n,L):            # Insertion de l'élément n dans la liste L
    for i in range(0,len(L)):  # supposée triée récursivement
        if L[i]>n:
            L=L[:i]+[n]+L[i:]
            return L
    return L+[n]

def recursiveInsertionSort(L):
   if len(L)==1:
       return L
   return insertion(L[len(L)-1],recursiveInsertionSort(L[:-1]))

Tout ou partie de cette page est issue de l'article Wikipédia « Tri par insertion » dans sa version du 29/04/2010.