Discuter:Tri par insertion

Un article de Wikipédia, l'encyclopédie libre.

	Tri par insertion fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Bon début	Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Faible	Cet article a été classé comme d'Importance faible selon le Tableau d'évaluation du projet. (Contester?)

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)

[modifier] 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)

[modifier] 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)

[modifier] erreur

hello hello,

il y a une erreur... :-)

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

Bye