A voir également:
- Tri a bulle recursive
- Video bulle whatsapp - Guide
- Tri excel - Guide
- Logiciel de tri de photos - Guide
- Tri automatique excel sans macro ✓ - Forum Excel
- Erreur de tri dans l'agence de distribution ✓ - Forum Consommation & Internet
2 réponses
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;
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
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
20 janv. 2008 à 18:05
20 janv. 2008 à 18:05
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:
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.
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.
12 mars 2012 à 11:18