Aller au menu - Aller au contenu

Le tri par insertion

Pour accéder à cette section
Connectez-vous !
connexion_rpx
Page 1 
Pseudo Commentaire
Page 1 
Hors ligne Anonyme # Posté le 02/03/2006 à 08:34:21

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 :p )
Hors ligne bluestorm # Posté le 02/03/2006 à 19:41:32
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

pas de bol, tu passes juste avant que je fasse la correction de pas mal de fautes :p
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 :-°
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne anonyme # Posté le 03/03/2006 à 08:50:47

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 :?
Hors ligne thom17 # Posté le 13/03/2006 à 16:02:48
Avatar

Études : FSA ULG

 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
 
Hors ligne bluestorm # Posté le 13/03/2006 à 16:07:56
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

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 ².
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne rushia # Posté le 06/09/2006 à 14:46:39
Avatar

Avis : Très bon

Études : Supélec

 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?
#LGDF: iPoulet vaincra !
 
Hors ligne samu # Posté le 24/10/2006 à 18:31:19

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
Hors ligne 0v3rb1t # Posté le 27/10/2006 à 21:48:06
C et C++, pas C/C++
Avatar
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
 
Hors ligne jo_le_coco # Posté le 30/10/2006 à 23:51:12
Avatar

Études : Ecole Centrale de Paris

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

Allez, 20 ! :p
Hors ligne Legényes # Posté le 18/12/2006 à 17:39:33
Avatar

Ville : Braine l'alleud
Pays : Belgique
Études : Ecole Supérieur d'Informatique de Bruxelles

 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
Hors ligne Weiouch # Posté le 25/12/2006 à 11:55:10
Avatar

 Bonjour,

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

++
<image>http://t0.gstatic.com/images?q=tbn:ANd9GcQ5Oaap_4FsQ9V5K4cFKY179d2PEPE_IbeuqngjP4bWUnqKfhXe</image>
 
Hors ligne Tristan.c # Posté le 27/12/2006 à 13:26:30

Études : ESSTIN

 Excellent tuto.

Note : 19

Merci :)
Hors ligne king92world # Posté le 16/02/2007 à 20:41:41
Avatar

Ville : Grenoble
Pays : France métropolitaine
Études : Polytechnique

 Excellent, exactement ce que j'avais besoin ;) !!

Cela mérite largement un 20 !
Hors ligne yoch # Posté le 25/11/2008 à 21:47:57
Avatar

 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/* 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...
Comprendre la messagerie électronique
Introduction à la programmation dynamique
Le backtracking par l'exemple : résoudre un sudoku
Bloquer du contenu avec le fichier hosts - La commande sed
Modifier une application Windows
 
Hors ligne yoch # Posté le 28/11/2008 à 12:46:50
Avatar

 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
Comprendre la messagerie électronique
Introduction à la programmation dynamique
Le backtracking par l'exemple : résoudre un sudoku
Bloquer du contenu avec le fichier hosts - La commande sed
Modifier une application Windows
 
Hors ligne madeinsousse # Posté le 28/03/2009 à 19:23:00
C juste un jeu ?
Avatar

 Bonjour ,
Cette implementation de l'algorithme de tri par insertion
Secret (cliquez pour afficher)
Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void tri_ins (long t [] , long n )

{
    unsigned i=0 , j=0 ;

    int v=0;

    for (i=1; i < n ; i ++ )//on concidere le premier element deja trier et on parcours les elements du tableau

    {
        v = t[i];//on sauvegarde la valeur de t[i] dans v
        j=i;// on assigne la position i dans celle de j

        while ( (j>0) && t [j-1]>v)//tant que j positive et l'élément précédent celui de t[j] est > a celui de t[i] faire
    {
        t [j] = t [j - 1];//on fait un décalage a gauche
        j -- ;// on décremente de -1 la position j
    }

    t [j] = v ;


et celle que vous avez proposez sont équivalentes en termes de complexité ?
Un programme informatique ne fait jamais ce que vous vouliez qu'il fasse,......
il fait seulement ce que vous lui dite de faire .

Troisieme loi de Greer
 
Hors ligne bluestorm # Posté le 28/03/2009 à 19:35:31
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Oui, elles sont équivalentes. La principale différence (qui ne change rien à la complexité) est le sens de parcours : ton code parcours la partie "déjà triée" du plus gros au plus petit, mon code du plus petit au plus gros.

Il n'y a pas une seule bonne manière de coder le tri par insertion, l'important c'est d'avoir compris le principe. Je vais sans doute modifier ma version pour la simplifier un peu, quand j'aurai le temps et la motivation nécessaire.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne bluestorm # Posté le 01/01/2010 à 17:51:03
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Mieux vaut tard que jamais : j'ai enfin intégré les remarques sur le code faites par candide. Ça a demandé de revoir aussi une bonne partie des explications, donc ça représente pas mal de travail (à l'échelle de la taille du tuto, qui reste raisonnable).

Je viens d'envoyer la nouvelle version en validation, je vous en reparlerai quand elle sera validée.

J'envisage dans un deuxième moment de reformuler un peu la partie complexité (à la lumière du tutoriel dédié, qui n'existait pas pendant l'écriture de ce tuto), mais je n'ai pas le temps pour l'instant.

Je mentionnerai peut-être aussi le Tri de Shell, comme proposé par yoch. Je n'en suis pas certain cependant, parce que c'est un tri à la théorie compliquée (on ne sait pas vraiment bien expliquer sa complexité), et qui au final reste moins intéressant en général que des tris par comparaisons optimaux, comme le tri fusion, qui restent plus facile à étudier.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne patate_violente # Posté le 05/01/2010 à 22:10:59
Avatar

Ville : Triel sur seine
Pays : France métropolitaine
Études : Université de Cergy-Pontoise

 merci pour ce cours !
J'ai appris une nouvelle façon intuitive de calculer la complexité avec le retournement et tout, carrément plus simple que mon cours

D'ailleurs je le poste tant qu'à faire vu qu'il est en latex déjà
Code : Autre
1
2
3
4
5
6
7
8
9

POUR j variant de 2 a n Faire        // C1 (* n-1)
        Carte <- tab[j]                        // C2 (* n-1)
        i <-- j-1                        // C3 (* n-1)
                Tant que (i>0) et (Carte < tab[i]) Faire        // C4 (* SUM(kj))
                        tab[i plus 1] <- tab[i]                // C5 (* SUM(kj))
                        i <-- i-1        // C6 (* SUM(kj))
                Fin tant que 
        tab[i plus 1 <-- Carte];        // C7 (* n-1)
Fin pour

Dans le pire des cas
C(n) = (C_{1}+C_{2}+C_{3}+C_{7})(n-1) + C_{4}\sum_{2}^{n}t_{ji} + (C5+C6) \sum_{2}^{n}(t_{j}-1)
avec a, b, c = constantes dependantes des C_{i} = an^{2}+bn+c = fonction quadiratique = ordre directeur^{2}

d'ailleurs que je n'ai toujours pas compris pourquoi tout ce bordel :o
donc merci à ce cours encore !
>> mon portfolio
 
Hors ligne psykie # Posté le 20/04/2010 à 19:28:06
/*Je suis une ZérO */
Avatar
close

Ville : Toulouse
Pays : France métropolitaine
Études : AFPA Balma

 Salut tout le monde,

s'il y a parmi vous des ZérOs (comme moi) qui n'ont pas tout saisi lors de la 1ière lecture, voire de celles qui suivent :-° sachez que vous vous posez sans doute les mêmes questions que moi...

J'ai ouvert un topic consacré à ce tuto ici, n'hésitez pas à y aller, vous y trouverez sans doute vos réponses ;)

Merci à Bluestorm pour son tuto :)
C : 100% | XHTML/CSS : 100% | PHP/MySQL : 100% | Java : 100% | C++ : in progress
Image utilisateur I LOVE C
 
Hors ligne timmalos # Posté le 22/04/2010 à 09:34:16
Avatar

Études : INSA Lyon

 J'ai bien aimé le tuto alors bravo, par contre, il y a un problème avec la license : En officiel c'est Copie non autorisé, et à la fin du tutoriel tu mets Creative Commons, on ne sait plus qui croire ;)
Image utilisateur
 
Hors ligne vswildcat # Posté le 15/06/2010 à 21:01:49
Avatar

 Apparement c'est la pratique, donc j'ai quelques questions, postées ici dans le forum.
Hors ligne Maëlan # Posté le 13/06/2011 à 16:58:10
Avatar

 Merci pour ce tutoriel Bluestorm, simple et clair :)

En revanche quelque chose me dérange sur ce code (le 1er de ton tuto) :
Code : C
1
2
3
4
5
6
7
void inserer(int element_a_inserer, int tab[], int taille_gauche)
{
    int j;
    for (j = taille_gauche; j > 0 && tab[j-1] > element_a_inserer; j--)
      tab[j] = tab[j-1];
    tab[j] = element_a_inserer;
}

À la ligne 4, si tu arrives à j==0, d'accord tu sors de ta boucle, mais avant tu auras lu tab[j-1], soit tab[-1] (pour le test du for) ; ça peut causer une erreur de segmentation, non ? (même chose dans ta "version longue")


ÉDIT (ne pas créer un nouveau message pour rien) : Ah, merci beaucoup Bluestorm, j'ai appris quelque chose aujourd'hui :)
© Message rédigé sous la seule propriété intellectuelle de son auteur Maëlan, et protégé contre toute reproduction partielle ou totale par l’ACTA (je vous remercie).
Logo de Xubuntu

Ne pas passer la main à travers l’enclos des loups.
Ne pas nourrir les lamas.
Ne pas utiliser de flash pour photographier les poneys.
Ne pas se moquer des manchots.

Un alias bien pratique : alias Taurre='cat http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf | grep TOPIC'. À ceux qui comprendront. ;)
 
Hors ligne bluestorm # Posté le 13/06/2011 à 18:45:40
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

C'est une bonne question, mais en C (et en fait dans la plupart des langages de programmation) les opérateurs logiques ont un comportement qu'on appelle "court circuit" : ils évaluent le membre de gauche et, s'ils peuvent déjà renvoyer une réponse, ils le font directement sans évaluer le membre de droite. Donc ici, dans le cas où j > 0 est faux, la boucle sort tout de suite sans même tester tab[j-1] (heureusement).

Plus précisément, le && répond "faux" directement si son terme de gauche est faux, et le || répond "vrai" directement si son terme de gauche est vrai.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne anouarattn # Posté le 06/12/2011 à 20:28:23

Études : Faculté des sciences de Rabat

 je pense qu'il faut mettre tab[j-1] = element_a_inserer; au lieu de tab[j] = element_a_inserer;

sinon ça na pas de sens de faire deux affectations l'une après l'autre
tab[j] = tab[j-1];
tab[j] = element_a_inserer;
Hors ligne bluestorm # Posté le 07/12/2011 à 01:20:15
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Les deux affectations ne sont pas faites l'une après l'autre : entre un tour de boucle (`tab[j] = tab[j-1]`) et l'affectation après la sortie de boucle il y a toujours l'action de mise à jour de la boucle (ici `j--`) qui est effectuée.

Je t'encourage à tester le code actuel et le code avec la modification que tu proposes, pour voir si cela marche bien.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne anouarattn # Posté le 17/12/2011 à 21:34:05

Études : Faculté des sciences de Rabat

 a oui merci
car sans {}, ok ok j'ai compris
voici une version d'insertion d'une valeur dans un tableau trie , seulement avec la notion de pointeur

Code : C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

int main()
{
    int *T,n,i,val    ;



    /* taille de T */

    printf("donner la taille du tableau");
    scanf("%d",&n);
    T=(int *)malloc((n+1)*sizeof(int));

    /* remplissage de T */

    for(i=0;i<n;i++)
    {
        printf("T[%d] = ",i);
        scanf("%d",(T+i));
    }

    /* lecture de T */
    for(i=0;i<n;i++)
    {
        printf("\nT[%d] = %d\n",i,*(T+i));
    }

    /*  la valeur a inserer */
    printf("\n\nentrer la valeur a inserer dans le tableau\n\n");
    scanf("%d",&val);


    /*  triage */

    for(i=n-1;i>=0 && *(T+i)>= val;i--)
    {
        *(T+i+1)=*(T+i);
    }
    *(T+i+1)=val;


    /* lecture de T */
    for(i=0;i<n+1;i++)
    {
        printf("\nT[%d] = %d\n",i,*(T+i));
    }


}
Pour accéder à cette section
Connectez-vous !
connexion_rpx