[Plan du site] Vous êtes ici --- > Le Site du Zéro > Les tutoriels > Non-Officiels > Programmation > Algorithmique > Le tri par insertion > Lecture des commentaires

Le tri par insertion

Vous devez être inscrit pour pouvoir poster des messages

Page : 1

Pseudo

Commentaire

Page : 1

iPoulet

# Posté le 02/03/2006 à 08:34:21 - Ce membre a mis la note : 20

Groupe : Membres

C'est un excellent tuto. Que dire d'autre ? Peut-être que certains rechigneront à le lire, mais ça sera à leur tord.

(Y'a des fautes d'orthographe quand même

)

Étoilé
« Eĉ guto malgranda, konstante frapante, traboras la monton granitan »

bluestorm

# Posté le 02/03/2006 à 19:41:32 - Ce membre n'a pas mis de note

dont ask to ask

Groupe : Membres

pas de bol, tu passes juste avant que je fasse la correction de pas mal de fautes

J'ai utilisé des polices spéciales pour les variables, donc ca devrait être plus lisible, et j'ai remanié un peu certain bouts de mon explication, donc ca devrait être (un peu) plus compréhensible :-°

iPoulet

# Posté le 03/03/2006 à 08:50:47 - Ce membre a mis la note : 20

Groupe : Membres

A vrai dire je me suis limité aux codes sources j'ai pas lu tout le reste (notamment la troisième partie à laquelle faudra que je m'attelle plus sérieusement) :-°

Mais déjà rien qu'avec la comparaison avec les cartes et le code je crois avoir saisi donc...

Edit : par contre ça je comprends pas "Quand N est très grand, N(N-1) est approximativement égal à N², et le nombre de comparaisons de l'algorithme est donc d'environ N²/2, ou N*0.5 comparaisons. "

On passe de N**2/2 à N*0.5 :?

Étoilé
« Eĉ guto malgranda, konstante frapante, traboras la monton granitan »

thom17

# Posté le 13/03/2006 à 16:02:48 - Ce membre a mis la note : 18

Groupe : Membres

Exact, il manque un ²...
Je trouve l'idée intéressante. Surtout si tu continues et que tu présentes d'autres tri. Le Quick Sort n'est pas très compliqué non plus... Et il est plus intéressant de connaitre celui la, car il est nettement plus efficace (qd les données d'entrée correspondent avec le choix du pivot)

Thomas
Ma page web

bluestorm

# Posté le 13/03/2006 à 16:07:56 - Ce membre n'a pas mis de note

dont ask to ask

Groupe : Membres

Je pensais faire d'autres tutos (et j'y pense toujours) mais pour l'instant je suis pas mal occupé, donc je préfère attendre d'avoir le plus possibles d'avis sur celui-là avant de me lancer.

Je corrige pour le ².

rushia

# Posté le 06/09/2006 à 14:46:39 - Ce membre a mis la note : 19

Groupe : Membres

J'avais vu ce tuto il y a pas mal de temps mais je n'avais pas eu le courage de le lire en entier. Maintenant que je l'ai fait je le trouve très interessant. Contrairement à un bon nombre des autres tutos (non-officiels) sur le C, tu presentes un algorythme (ce que je trouve plus utile que d'apprendre à mettre des couleurs dans la console :-°

). j'espère que tu trouvera le temps de faire des tutos sur d'autres algorythme aussi utile que celui-là.

NOTE : 19/20.

EDIT 1 : une erreur : le nom de la fonction qui permet d'inserer un élément passe de "inserer" à "inserer_element"
EDIT 2 : Il y a un petit truc que je n'arrive pas à expliquer. Dans la fonction inserer()
Code : C

gauche[taille] = element_a_inserer;

ce trouve dans la boucle for alors que dans le code version longue, il se trouve à l'extérieur de cette même boucle. Pouquoi?

samu

# Posté le 24/10/2006 à 18:31:19 - Ce membre n'a pas mis de note

Groupe : Membres

excellent tutoriel je commence l'algorithmique et j'ai trouvé ce tuto très clair et très interessant. Sa serais bien que tu en fasse d'autre

0v3rb1t

# Posté le 27/10/2006 à 21:48:06 - Ce membre a mis la note : 18

C et C++, pas C/C++

Groupe : Bannis

j'ai un peu lu et compris le principe, je lierai tout plus tard, mais en tout cas c'est expliqué en détail et intelligiblement, bravo.

note: 18.

SMART_TELNET(projet à reprendre)
[C]Tutoriel ANSI
[C]Bien programmer en C -ed-
[C]Développez
[C]Wikibooks
[C]Sockets
[C-python]GTK+
[C-algo]France-IOI
[C]Algorithmique

jo_le_coco

# Posté le 30/10/2006 à 23:51:12 - Ce membre a mis la note : 20

Groupe : Membres

Merci pour ce tuto riche, complet, efficace, clair, [...,[...]]

Allez, 20 !

Legényes

# Posté le 18/12/2006 à 17:39:33 - Ce membre a mis la note : 17

Groupe : Membres

Très bon tuto.

Peut être rajouter apres le chapitre sur la complexité, ce petit lien
Coparatif des différents algorithms de tris

Encore bravo

Weiouch

# Posté le 25/12/2006 à 11:55:10 - Ce membre a mis la note : 18

Groupe : Membres

Bonjour,

Clair, net et précis...merci beaucoup, beau travail !

++

Tristan10101

# Posté le 27/12/2006 à 13:26:30 - Ce membre a mis la note : 19

Enjoy !

Groupe : Membres

Excellent tuto.

Note : 19

Merci

king92world

# Posté le 16/02/2007 à 20:41:41 - Ce membre a mis la note : 20

Groupe : Membres

Excellent, exactement ce que j'avais besoin

!!

Cela mérite largement un 20 !

The SushiMan

Projet en C++ et Qt4 :
Modern War ( stratégie tour par tour ) : 6 %

yoch

# Posté le 25/11/2008 à 21:47:57 - Ce membre a mis la note : 14

Groupe : Membres

L'implémentation C a été sérieusement critiquée ici, je cite :

Citation : candide

Le code de bluestorm comporte deux maladresses d'ordre algorithmique. Je rappelle le code :

Code : C

/* 01 */ void tri_insertion(int tab[], int taille)
/* 02 */ {
/* 03 */        int i, j;
/* 04 */        for(i = 1; i < taille; ++i)
/* 05 */        {
/* 06 */               int element_a_inserer = tab[i];
/* 07 */               for(j = 0; j < i; ++j)
/* 08 */               {
/* 09 */                      int element_courant = tab[j];
/* 10 */                        if (element_a_inserer < element_courant)
/* 11 */                      {
/* 12 */                             tab[j] = element_a_inserer;
/* 13 */                          element_a_inserer = element_courant;
/* 14 */                      }  
/* 15 */               }
/* 16 */               tab[i] = element_a_inserer;
/* 17 */        }
/* 18 */ }

1ère maladresse : ligne 7 : il n'y aucune raison qu'on parcoure (indice i) toutes les cartes déjà classées (indice j) pour faire l'insertion.

2ème maladresse : lignes 9 à 14 : il n'y pas de raison de systématiquement échanger avec un tampon, il y a juste une seule sauvegarde à faire (la valeur à insérer) ce qui libère une place, place qu'on retrouve en cascade quand on fait le décalage vers la droite (en fait on permute circulairement les valeurs).

2 codes nettement meilleurs, je crois, sont par ailleurs proposés dans cette même discussion...

Tutos en ligne
Comprendre la messagerie électronique
Bloquer du contenu avec le fichier hosts
Modifier une application Windows

yoch

# Posté le 28/11/2008 à 12:46:50 - Ce membre a mis la note : 14

Groupe : Membres

Bon, je suis repassé sur le tuto, les explications ont le mérite d'être très claires. (je mettrais bien 16/20, mais je ne peux plus...)

Peut-être conviendrait-il de parler des optimisations possibles du tri par insertion :
Citation : Wikipédia

Propriétés

[...]

Si une liste chaînée est utilisée, il n'y a plus d'échanges à faire (les insertions se font en temps constant), mais le nombre de comparaisons pour trouver l'emplacement où insérer reste de l'ordre de N²/4 et il est difficile d'optimiser cette recherche.

A contrario, avec un tableau il est possible de faire un nombre de comparaisons de l'ordre de N.ln(N) en utilisant une recherche par dichotomie pour trouver l'emplacement où insérer l'élément.

[...]

Optimisations possibles

On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés.

Ainsi que mentionner le tri de shell, qui est une optimisation du tri par insertion :

http://fr.wikipedia.org/wiki/Tri_de_Shell
http://www.siteduzero.com/tutoriel-3-3 [...] de-shell.html

Tutos en ligne
Comprendre la messagerie électronique
Bloquer du contenu avec le fichier hosts
Modifier une application Windows

Vous devez être inscrit pour pouvoir poster des messages

Tutoriels

Communauté

Mon compte

Recherche

Livre d'or

Publicité

Le tri par insertion