Discussion:Tri par insertion

Stabilité code OCaml

Sauf erreur de ma part, le tri produit par le code OCaml n'est pas stable. Zandr4 (d) 12 août 2008 à 17:15 (CEST)

Après vérification, le tri n'était pas stable. J'ai modifié le code, en mettant <=au lieu de <

let rec triInsertion = 
	let rec insere elem = function
	[] -> elem :: []
	| hd::tl as ls -> 
		if fst elem < fst hd then elem::ls
		else hd :: (insere elem tl)
	in 
function
[] -> []
| hd::tl -> insere hd (triInsertion tl)

let l = (1,'a') :: (0, 'a') :: (3,'b') :: (5,'a') :: (3,'c') :: (6,'a') :: []

let display e = Printf.printf "%c" (snd e);;
List.map display (triInsertion l)

(*affiche aacbaa au lieu de aabcaa *)

N²/4 ou N²/2 comparaisons

Le nombre de comparaison est de N²/2 dans un "code optimisé". J'entends par là si l'on ne continue plus à faire de comparaisons lors des décalages après avoir inséré un élément (puisque les éléments à décaler sont déjà triés).

Par ailleurs, le nombre d'échanges ne veut rien dire, il n'y en a aucun en dès lors que l'on utilise des listes (OCaml ou listes chaînés C...). Et comme il est dit dans l'article, même en utilisant des tableaux en C, on peut comme le fait le code C donné décaler les éléments sans réaliser d'échange... Je ne vois donc pas l'utilité de donner cette information...

Zandr4 (d) 11 août 2008 à 19:18 (CEST)

je ne comprend pas l'algorithme par insertion?

En fait, si tu as un tbleau, tu vas considérer ce tableau selon deux parties. une partie des éléments déjà triés. Une partie des éléments à trier. Au départ de l'algo, ta partie triée, c'est la première case du tableau seulement. Tu regardes donc la case 2 du tableau qui est le premier élément de la partie non triée. et tu l'insères dans la partie triée à sa place (avant la case 1 ou tu la laisses ou elle est en fait. tu as alors 2 cases dans la partie triée et le reste à trier. Tu recommences en prenant la case 3 que tu insères là ou elle doit être dans la première partie. Et ainsi de suite.

J'ai peut être pas été trés clair mais à appliquer c'est vraiment comme qd tu tries tes dossiers comme dit dans l'article. Tipiac 25 oct 2004 à 20:54 (CEST)

N²/4 comparaisons ?

Euh, si l'on insère par dichotomie, à chaque insertion c'est en log N, non ? Dans ce cas je m'attendrais à du N log N.

Même en insérant par dichotomie il me semble qu'il y a un coût linéaire de décalage des éléments du tableau
Bluestorm 2 mars 2007 à 12:15 (CET)

Je suis d'accord avec cette critique. Le nombre de comparaisons est bien en Θ(n log n). Et certes, si on a la mauvaise idée d'utiliser un "array" (tabeau) alors qu'on veut implémenter un algo par insertion (:facepalm :facepalm), alors le nombre d'affectations est en effet en Θ(n²) en raison des insertions pour lesquelles il faut décaler tout le contenu. *Mais* c'est tout simplement une grossière erreur d'implémentation !! Si on sait qu'on aura besoin d'insertions (comme le nom de l'algo l'indique), il serait totalement stupide d'utiliser des "array", on doit *évidemment" utiliser une implémentation adaptée, par exemple celle d'un "balanced tree" qui permet aussi bien l'accès direct à n'importe quel élément ainsi que l'insertion à n'importe quel endroit avec une complexité de Θ(log n), et dans ce cas on a un tri par insertion qui est en Θ(n log n). Or, la façon dont la structure de données est implémentée est "transparente" dans l'algorithme qui utilise une fonction "insert()" sans se soucier ce que ça fait. Après il faut choisir l'implémentation qui convient le mieux pour la structure utilisée pour la liste/tabeau des données, en fonction des besoins et des coûts pour une implémention donnée. — MFH 28 avril 2023 à 00:43 (CEST)

Gros doute à propos du code en C proposé

Je fais un petit exposé sur les tris et j'ai implémenté la version de ce tri par insertion en place, et le résultat est incohérent ... Chez moi, dès qu'il trouve une valeur à déplacer, il l'a duplique indéfiniment, ce qui fait que la première clé à déplacer se copie/colle sur toutes les clés suivantes, jusqu'à la fin.

Bref, j'ai modifié le code de décalage :

/* décalage avant des valeurs de t entre p et i */ for (j = i-1; j>=p; j++) {

   t[j+1] = t[j];

}

Le code de décalage allait dans le mauvais sens, d'où la duplication. Ici, toutes les valeurs remontent jusqu'à la position de la valeur à déplacer, et cette dernière est enfin placé en i.

--SilverEleven 31 mai 2007 à 10:45 (CEST)

erreur

hello hello,

il y a une erreur... :-)

on passe un tableau d'entier mais on le traite comme des doubles...

Bye

Réorganisation

Bonjour,

Je propose une réorganisation de l'article, pour les raisons suivantes :

• Je pense que le fait que l'algorithme est peu efficace en général devrait être mentionné dans l'introduction, pas dans les propriétés.
• L'introduction parle indistinctement de listes puis de tableaux. À mon avis, il vaudrait mieux décrire d'abord l'algorithme pour les tableaux (c'est beaucoup plus courant), et parler de listes seulement dans un paragraphe spécifique.
• L'introduction décrit une méthode en deux phases (trouver la position, puis décaler) pour chaque élément, ce qui n'est pas l'approche la plus courante. La méthode en une passe n'est décrite que par les implémentations (et pas toutes).
• Le paragraphe sur les propriétés parle du nombre d'échanges et puis critique cela, alors que cette façon de faire n'est décrite nul part.
• La partie sur la dichotomie aurait plus sa place dans le paragraphe optimisations.
• Le pseudo-code est tout à la fin, à mon avis, il vaudrait mieux le mettre avant de parler des propriétés de l'algorithme.

Je prépare une nouvelle version sur la page Utilisateur:Nordald/test. N'hésitez pas à me faire part de vos remarques.

Nordald (d) 18 avril 2010 à 14:33 (CEST)

Le code était buggé.

Après toutes ces années....

Un jour, quelqu'un a décidé de modifier cette page pour faire partir les indices de 0. Pourquoi pas, maintenant que Fortran et Pascal sont moins populaires dans l'enseignement, on peut choisir de se plier aux conventions de C et des langages dérivés concernant les tableaux.

Mais du coup, la boucle principale, donc le corps sert à replacer l'élément d'indice i de façon à ce que la "tranche" T[0:i] soit ordonnée, cette boucle donc ne doit pas aller jusqu'à N, mais N-1.

Incidemment elle peut partir de 1, parce qu'on n'a pas besoin de replacer T[0], au départ.

2A01:E35:2EBF:AE80:2677:3FF:FE39:26F0 (discuter)mb