tri insertion par méthode récursive Fermé

Question

Bonjour,
j'ai un probléme, je veux savoir comment trier un tableau en utilisant le tri par insertion par la méthode récursive, aidez moi s'il vous plait et merci.

hassib · Accepted Answer

Voici une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par insertion : 
Procedure Tri_Ins (Var t: TAB; n: integer);  
Var aux,i : integer;  
begin  
        If n > 1 Then  
             begin  
                  Tri_Ins (t,n - 1);  
                  If t[n] < t[n - 1] Then  
                  Begin  
                     aux:= t[n];  
                     i := n;  
                     Repeat                          
                        t[i] := t[i - 1];  
                        i := i - 1;  
                     Until (i = 1) Or (aux > t[i - 1]);  
                     t[i] := aux;  
                  End;

Mahmah · Answer

Bonjour,

Je vois la chose un peu comme la récursivité vue en math: On suppose que le résultat d'un appel est un tableau déjà trié
Ensuite on cherche dans ce tableau trié où insérer une valeur

ainsi en pseudo code je verrais une chose du style:


sort ( tab )
{
   // Cas d'arrêt :
   si taille du tableau est 0 alors il est trié (on pourrait s'arrêter à 1 mais on gère ainsi le cas ou le tableau original est vide)
   End

   sinon:
   // garder une des valeurs du tableau (par exemple la première)
   var valeur = tab[0]

   // trier le reste du tableau
   sort ( tab + 1 )   // où tab + 1 est le tableau à partir de la 2me case

   // Insérer valeur dans le tableau maintenant trié
   tant que valeur est <comparaison voulue> par rapport à tab[i]
   augmenter l'indice jusqu'à trouver où insérer valeur

   //   On a trouvé l'indice où mettre valeur
   décaler tous les éléments à partir de i (i compris)
   mettre valeur à l'indice i
   End
}


Je ne vois pas de solution sans décaler chaque fois tous les éléments. Cela reste de l'insertion.

On passera aussi en paramètre la taille du tableau si le langage d'implémentation ne permet pas de la déduire de la variable tab.
avec alors une récursivité sort ( tab + 1, taille - 1 )

M.

Tri insertion par méthode récursive

2 réponses

Discussions similaires