Partage

Tri par insertion

je comprends pas ce tri..

1 2 >>

30 décembre 2009 à 20:56:42

Salut tlm,

donc voila je dois faire une fonction de Tri par insertion en C et le probleme c'est que j'ai bien compris le tri par bulle et par selection mais j'arrive pas a comprendre qu'est ce que le tri par insertion..
donc si je comprend pas comment ca marche je peux pas commencer a ecrire l'algorithme.

Voila la definition que je n'arrive tout de meme pas a comprendre (je vous serez reconnaissant de m'expliquer svp) :

Citation

Tri par insertion
Le tri par insertion est le tri le plus efficace sur des listes de petite taille. C'est pourquoi il est utilisé par d'autres méthodes comme le tri rapide (ou quicksort). Il est d'autant plus rapide que les données sont déjà triées en partie dans le bon ordre.
Le principe de ce tri est très simple: c'est le tri que toute personne utilise naturellement quand elle a des dossiers (ou n'importe quoi d'autre) à classer. On prend un dossier et on le met à sa place parmi les dossiers déjà triés. Puis on recommence avec le dossier suivant.
Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans l'ordre. Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément qu'on considère. Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré à sa place dans la partie déjà triée. On peut aussi faire une recherche par dichotomie sur les tableaux.

Pouet_forever

30 décembre 2009 à 21:09:36

C'est là que bluestorm intervient !
Essaye de ne pas trop regarder son code mais de l'implémenter toi-même

http://www.siteduzero.com/tutoriel-3-3 [...] nsertion.html

Mathieu__71

30 décembre 2009 à 21:22:42

en fait le principe du tri par insertion c'est qu'a chaque valeur rentré tu la compare aux autres valeurs quand tu a trouvé sa place tu décale toutes les valeurs suivantes vers la droite et tu insère ta valeurs et ainsi de suite ...

candide

30 décembre 2009 à 21:29:46

[délestage]

Pouet_forever

30 décembre 2009 à 21:33:41

Ah ... désolé

(je n'ai pas lu son tuto je sais juste qu'il est présent sur le site :euh:

)
Mais ça m'étonne de la part de bluestorm :euh:

candide

30 décembre 2009 à 21:40:24

Citation : Pouet_forever

(je n'ai pas lu son tuto je sais juste qu'il est présent sur le site )

Ben oui, c'est un peu ça le problème sur Internet : tout le monde copie ou cite tout le monde sans prendre le soin de vérifier.

Citation : Pouet_forever

Mais ça m'étonne de la part de bluestorm

Ben moi aussi !

Alienore

30 décembre 2009 à 23:52:47

Le principe est assez simple.
On suppose que les n premiers éléments du tableau sont triés. On va donc ajouter le n+1ème élément de ce tableau au tableau trié (à la bonne place évidemment).
Il est évident qu'un tableau à 1 élément est nécessairement trié (cas de base).
J'ai donné une vision récursive de la chose mais on peut très facilement le passer en itératif.

Après, pour aller ranger l'élément courant, je vois principalement 2 méthodes :
- reculer l'élément jusqu'à trouver une valeur qui lui est inférieure.
- chercher sa place à l'aide d'une fonction de recherche et reculer l'élément jusqu'à cette place.

La première méthode exige moins de tests si les valeurs sont presque dans l'ordre croissant tandis que l'autre en demande moins si les valeurs sont presque rangées dans l'ordre décroissant.
Ne sachant généralement pas comment sont mises les valeurs, l'implémentation n'a pas trop d'importance.

J'espère que mes explications t'auront aidé.

candide

31 décembre 2009 à 0:04:53

Citation : Alienore

On suppose que les n premiers éléments du tableau sont triés. On va donc ajouter le n+1ème élément de ce tableau au tableau trié (à la bonne place évidemment).
Il est évident qu'un tableau à 1 élément est nécessairement trié (cas de base).
J'ai donné une vision récursive de la chose mais on peut très facilement le passer en itératif.

Tiens, je serais curieux de voir cette implémentation récursive (rappel : "In C ode we trust !")

Sans parler du manque de clarté de tes explications à l'endroit de quelqu'un qui dit ne pas avoir compris ce qu'est le tri par insertion

Citation : Alienore

Après, pour aller ranger l'élément courant, je vois principalement 2 méthodes :
- reculer l'élément jusqu'à trouver une valeur qui lui est inférieure.

Pas clair.

Citation : Alienore

- chercher sa place à l'aide d'une fonction de recherche et reculer l'élément jusqu'à cette place.

Pas clair.

Tu n'exprimes pas clairement les trois étapes de la boucle d'un tri dit "par insertion" :
-- la recherche de l'emplacement
-- le décalage
-- l'insertion.

Arthurus

31 décembre 2009 à 0:25:24

Citation : candide

(rappel : "In C ode we trust !")

Ça a changé à ce que je vois

(y avait pas d'espace avant pour faire le jeu de mot)

Alienore

31 décembre 2009 à 2:03:23

///prend un tableau et sa taille pour le trier du plus petit au plus grand
void tri_insert_rec(int* tab, int taille)
{
  int i, tmp;
  ///si le tableau est de taille inférieure ou égale à 1, on n'a rien à faire
  if(taille <= 1)
    return;
  ///sinon, on commence par trier le tableau de taille taille-1
  tri_insert_rec(tab,taille-1);
  ///puis on va placer l'élément que l'on veut ajouter
  tmp = tab[taille-1];
  for(i = taille - 2;i >= 0;i--)
  {
    if(tab[i] > tmp)
    {
      tab[i+1] = tab[i];
    }
  }
  ///maintenant, i + 1 est la place de l'élément
  tab[i + 1] = tmp;
}

Je n'ai pas testé le cas où le tableau est nul car ça utiliserait encore plus de temps de calcul de toujours vérifier que le pointeur (que l'on ne change pas) est différent de NULL

Mathieu__71

31 décembre 2009 à 11:59:17

bonjours, voici un petit exemple de tri par insertion que j'ai fais il y a pas super longtemps.

#include <stdio.h>

main()
{
	int tab[20];
        int nb_val;
        
	int nombre_valeurs();
	void affiche_valeurs(int nb_val,int *tab);
	void tri(int nb_val, int *tab);     
        
        nb_val=nombre_valeurs();
        tri(nb_val,tab);
        affiche_valeurs(nb_val,tab);

}

int nombre_valeurs()
{
	int taille;
	do
        {
        	printf("Combien de valeurs desirez vous saisir (<20) : ");
        	scanf("%d",&taille);
        }
        while(taille<=0 ||taille>20);
    return taille;
}

void affiche_valeurs(int nb_val,int *tab)
{
	int i;
	printf("apres le tri : ");
        for(i = 0; i < nb_val; i++)
        {
		printf("%d ", tab[i]);
	}
		printf("\n");
}

void tri(int nb_val, int *tab)
{
	int element_a_inserer,element_courant,i,j,e,n=0;
	for(e=0;e<nb_val;e++)
        {
		printf("Entrez un nombre : ");
		scanf("%d",&tab[e]);
		n++;
        
        	for(i = 1; i < n; ++i)
        	{
               		element_a_inserer = tab[i];
               		for(j = 0; j < i; ++j)
               		{
                      		element_courant = tab[j];
                      		if (element_a_inserer < element_courant)
                      		{
                          		tab[j] = element_a_inserer;
                          		element_a_inserer = element_courant;
                      		}  
               		}
               		tab[i] = element_a_inserer;
        	}
	}
}

candide

1 janvier 2010 à 1:40:53

Citation : Mathieu__71

void tri(int nb_val, int *tab)
{
	int element_a_inserer,element_courant,i,j,e,n=0;
	for(e=0;e<nb_val;e++)
        {
		printf("Entrez un nombre : ");
		scanf("%d",&tab[e]);
		n++;
        
        	for(i = 1; i < n; ++i)
        	{
               		element_a_inserer = tab[i];
               		for(j = 0; j < i; ++j)
               		{
                      		element_courant = tab[j];
                      		if (element_a_inserer < element_courant)
                      		{
                          		tab[j] = element_a_inserer;
                          		element_a_inserer = element_courant;
                      		}  
               		}
               		tab[i] = element_a_inserer;
        	}
	}
}

Ce tri fait des choses inutiles. D'une part, une fois que l'indice j d'insertion a été repéré, la comparaison element_a_inserer < element_courant n'est plus utile. En outre, lorsqu'il faut décaler, ce code fait 2 fois trop d'affectation. D'autre part, si element_a_inserer < element_courant est toujours faux, on affecte tab[i] à lui-même (ligne 22 de l'extrait que j'ai affiché ci-dessus).

Une fois de plus, il apparait que coder convenablement un tri par insertion n'est pas si simple. Pourtant, il s'agit juste de singer la façon de trier une main avec des cartes.

Arthurus

1 janvier 2010 à 3:14:13

Citation : Alienore

///prend un tableau et sa taille pour le trier du plus petit au plus grand
void tri_insert_rec(int* tab, int taille)
{
  int i, tmp;
  ///si le tableau est de taille inférieure ou égale à 1, on n'a rien à faire
  if(taille <= 1)
    return;
  ///sinon, on commence par trier le tableau de taille taille-1
  tri_insert_rec(tab,taille-1);
  ///puis on va placer l'élément que l'on veut ajouter
  tmp = tab[taille-1];
  for(i = taille - 2;i >= 0;i--)
  {
    if(tab[i] > tmp)
    {
      tab[i+1] = tab[i];
    }
  }
  ///maintenant, i + 1 est la place de l'élément
  tab[i + 1] = tmp;
}

Je n'ai pas testé le cas où le tableau est nul car ça utiliserait encore plus de temps de calcul de toujours vérifier que le pointeur (que l'on ne change pas) est différent de NULL

T'es sûr que ça marche ton truc ??

int tab[] = {83,86,77,15,93,35,86,92,49,21};
tri_insert_rec(tab,10);
affiche(tab,10);

arthurus@Arthurus-Laptop:~/sdz$ ./toto
21 49 92 93 93 93 86 93 93 93

elmcherqui

1 janvier 2010 à 4:08:15

Citation : candide

Tiens, je serais curieux de voir cette implémentation récursive (rappel : "In C ode we trust !")

bien entendu je suis daccord

.

voila le premier code que j'ecris en 2010 sous l'effet du someil ( il est 03h du mat )

, oui oui je passe le nouvel an devant mon PC et alors c'est le seul qui me comprend dans ce monde illogique !

ce code est juste pour montrer que tous algorithme ieratif a un equivalent en recursif et vice versa , le passage de l'un a l'autre est dur selon la complexite et la nature du programme .

programme commenté compilé sous VC++2008 et sous code::block en C sans problemes .

pour le tri insertion en recursif si vous utilisez une entree tres grande votre pile ne va pas suivre et c'est le stack overflow direct .
pour l'iteratif y'a pas de limites .

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX 200 //200 nombres sa suffit pour trier , right ?
#define FAUX 'F'
#define VRAI 'V'
#define BOOL char

int tabATrier[MAX];


BOOL estTrie()
{
    int num;
	for( num=0;num<MAX-1;num++)
		if( tabATrier[num] > tabATrier[num+1])
			return FAUX;
	return VRAI;
}

void triVersionIterative() //jusque la tous est normal
{
    int cle,valCle,iCle;

	for(cle = 1;cle<MAX;cle++)
	{
        iCle = cle-1;
        valCle = tabATrier[cle];
		while( iCle >= 0 && valCle < tabATrier[iCle] )
			tabATrier[iCle+1] = tabATrier[iCle--];
		tabATrier[iCle+1] = valCle;
	}
}
//recursif fait par analogie
void triVersionRecursive(int cle ,int valCle,int iCle )
{
	if( cle >= MAX )
		return; // si il arrive ici le programme se termine , heuresement pour notre pile 
	if( iCle >=0 && valCle < tabATrier[iCle] ) // ici la boucle imbriquee toujours la premiere
	{
		tabATrier[iCle+1] = tabATrier[iCle];
		triVersionRecursive(cle,valCle,iCle-1);
	}
	else {
		tabATrier[iCle+1] = valCle; //sa veut dire que la boucle secondaire a finis
		triVersionRecursive(cle+1,tabATrier[cle+1],cle); // ici pour la boucle primaire et on recommence !!!
	}
}

void affiche()
{
    int num;
	for(num=0;num<MAX;num++)
		printf("%d ",tabATrier[num]);
	printf("\n");
}

int main()
{
    int num;

	srand((unsigned int ) time(NULL));
	for(num=0;num<MAX;num++)
		tabATrier[num] = rand();

	if( rand() % 2 == 0 )//choisi l'iteratif ou le recursif aleatoirement une chance sur deux
        triVersionIterative();
    else
        triVersionRecursive(1,tabATrier[1],0);


	if( estTrie() == VRAI )
		printf("oui monsieur vous l'avez trie ...");
	else
		printf("ehhh non vous vous etes gourre ...");



	printf("\n");
	return 0;
}

voilou bonne nuit !!!

EDIT : le rendu de l'indentation du Zcode est bizarre

chez moi c'est tres bien fait .

Alienore

1 janvier 2010 à 9:43:33

Je pense que mon erreur est au moment de placer l'élément à sa place. Je ne m'arrête pas à la place que je voulais.

///prend un tableau et sa taille pour le trier du plus petit au plus grand
void tri_insert_rec(int* tab, int taille)
{
  int i, tmp;
  ///si le tableau est de taille inférieure ou égale à 1, on n'a rien à faire
  if(taille <= 1)
    return;
  ///sinon, on commence par trier le tableau de taille taille-1
  tri_insert_rec(tab,taille-1);
  ///puis on va placer l'élément que l'on veut ajouter
  tmp = tab[taille-1];
  ///on met le test qui était dans le if en tant que condition de continuité
  ///maintenant, ça devrait fonctionner
  for(i = taille - 2;i >= 0 && tab[i] > tmp;i--)
  {
    tab[i+1] = tab[i];
  }
  ///maintenant, i + 1 est la place de l'élément
  tab[i + 1] = tmp;
}

Je n'avais pas mis la bonne condition d'arrêt.

Arthurus

1 janvier 2010 à 9:49:37

Cool, elle n'explose pas très vite à ce que je vois.
Contrairement à celle de elmcherqui qui crack dès qu'on attend les 4 chiffres (j'ai été obligé de forcer le pauvre valgrind pour allouer plus d'espace pour la pile afin de tester les perfs).

candide

1 janvier 2010 à 10:17:03

Citation : elmcherqui

Citation : candide

Tiens, je serais curieux de voir cette implémentation récursive (rappel : "In C ode we trust !")

bien entendu je suis daccord .

//recursif fait par analogie
void triVersionRecursive(int cle ,int valCle,int iCle )
{
	if( cle >= MAX )
		return; // si il arrive ici le programme se termine , heuresement pour notre pile 
	if( iCle >=0 && valCle < tabATrier[iCle] ) // ici la boucle imbriquee toujours la premiere
	{
		tabATrier[iCle+1] = tabATrier[iCle];
		triVersionRecursive(cle,valCle,iCle-1);
	}
	else {
		tabATrier[iCle+1] = valCle; //sa veut dire que la boucle secondaire a finis
		triVersionRecursive(cle+1,tabATrier[cle+1],cle); // ici pour la boucle primaire et on recommence !!!
	}
}

Pourquoi pas en effet même si c'est assez artificiel. En particulier l'interface du tri devrait être du genre :

void triVersionRecursive(int tabATrier[], int nb_el)

ce qui n'est pas du tout le cas chez toi. Un bon design de fonction ne doit posséder en paramètres que ce qui correspond à la tache à exécuter.

GurneyH

1 janvier 2010 à 15:57:08

Un tri insertion récursif? Intéressant!

Par contre effectivement, la pile n'apprécie pas.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define N   10000

int descendingCmp(int a, int b)
{
    return (a >= b);
}

int ascendingCmp(int a, int b)
{
    return (a <= b);
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void insert(int *t, int crt, size_t i, size_t j, int(*cmp)(int, int))
{
    if (j == i)
    {
        t[i] = crt;
        return ;
    }

    if (cmp(t[j], crt))
        swap(&t[j], &crt);
    insert(t, crt, i, j + 1, cmp);

}


void insertSortRec(int *t, size_t n, size_t i, int(*cmp)(int, int))
{
    if (i != n)
    {
        insert(t, t[i], i, 0, cmp);
        insertSortRec(t, n, i + 1, cmp);
    }
}



void insertSort(int *t, size_t n, int(*cmp)(int, int))
{
    insertSortRec(t, n, 0, cmp);
}




void fillTab(int *t, size_t n)
{
    size_t i;
    for (i = 0; i < n; ++i)
        t[i] = rand() % INT_MAX;
}



void test(int *t, size_t n)
{
    clock_t start;
    fillTab(t, n);

    puts("Test...");
    start = clock();
    insertSortRec(t, n, 0, descendingCmp);

    printf("Tableau trie en %f s : \n", (clock() - (double)start) / CLOCKS_PER_SEC);
}



int main(void)
{
    int t[N];

    srand((unsigned)time(NULL));

    test(t, N);

    return 0;
}

edit : correction de code en cours. :honte:

edit : code corrigé. :-°

Sauf que j'avais inversé les fonctions de comparaison. >_<

Là ça doit être bon. :-°

edit: Les fonctions de comparaisons étaient moches...

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

1 janvier 2010 à 16:24:30

Citation : GurneyH

edit : correction de code en cours.

elmcherqui

1 janvier 2010 à 17:40:33

Citation : candide

ce qui n'est pas du tout le cas chez toi. Un bon design de fonction ne doit posséder en paramètres que ce qui correspond à la tache à exécuter.

chose qui est impossible puisque il y'a deux boucles imbriquee , et donc on a besoin de ces parametres pour se passer les donnees entre chaque apel sinon on ne saura pas si on est dans la seconde boucle ou dehors . enfin c'est comme sa que je vois les choses , a moins d'utiliser un pointeur en parametre mais bon sa reviens au meme . si tu veux une jolie interface et bien refait la fonction adequate et met la fonction que j'ai ecrite dedans

.

EDIT : y'a pas d'edit ici circulez !!!

Alienore

1 janvier 2010 à 21:03:49

Pour une fois que ce n'est pas moi qui me complique la vie... La fonction que j'ai faite tient en 20 lignes (13 en enlevant les commentaires) et est récursive... Quel autre paramètre faut-il envoyer puisqu'on sait que le début du tableau est trié ?
Edit : On pourrait encore récursiver la manière de mettre l'élément à sa place mais ça n'aurait aucun intérêt. (déjà que ça n'a pas d'intérêt de récursiver une fonction que l'on a itérativement)

void tri_insert_ite(int tab[], int taille)
{
  int i, j, tmp;
  for(i = 1;i<taille;i++) ///le premier élément est déjà trié
  {
    tmp = tab[i];
    for(j=i-1;j>=0 && tab[j] > tmp;j++) ///tant que l'élément à trier est inférieur à l'élément considéré, on décale
    {
      tab[j+1] = tab[j];
    }
    tab[j + 1] = tmp;
  }
}

J'ai juste appliqué une manière de dérécursiver ce que j'avais fait (sans pour autant retracer les appels).

GurneyH

1 janvier 2010 à 22:41:12

@Alienore: une boucle for dans une fonction récursive.

Zeste de Savoir, le site qui en a dans le citron !

bluestorm

2 janvier 2010 à 0:58:37

Citation : candide

Citation : Pouet_forever

C'est là que bluestorm intervient !
Essaye de ne pas trop regarder son code mais de l'implémenter toi-même
http://www.siteduzero.com/tutoriel-3-3 [...] nsertion.html

Hélas, son code est assez mauvais, désolé de le redire, cf. ztri et des explications ici.

Une fois n'est pas coutume, j'ai pris le temps aujourd'hui de ré-écrire une grande partie de mon tutoriel pour répondre à ces commentaires qui traînent sur le forum depuis un certain temps.
Je m'excuse platement d'avoir été si lent à faire les modifications; je suis juste très occupé. Je m'attends à ce que la version actuelle ne soit encore pas parfaite (en particulier je n'exclus pas un petit bug très bête dans le code qui ferait que le tri ne marche pas, ou une autre blague du genre), mais j'ai fait des efforts pour que le code "intelligent" proposé soit présenté de façon naturelle, et pas balancé juste comme ça.

Pour la petite histoire, j'ai commencé par faire en deux temps "la version simple recherche + décalage" puis "la version optimisée sans recherche de l'emplacement à insérer", avant de me rendre compte qu'en changeant de point de vue on pouvait présenter la version la plus efficace directement, sans sacrifier la clarté de l'explication. Comme candide s'amuse à le répéter, et de moins point de vue ce n'est pas du tout ironique, écrire un bon tri par insertion ce n'est pas du tout simple.

Bref, voilà le code proposé actuellement par mon tutoriel (version longue, lire le tuto pour en savoir plus), inspiré (mais pas copié) d'une implémentation de candide traînant sur le forum :

void tri_insertion(int tab[], int taille)
{
   int i, j;
   for (i = 1; i < taille; ++i) {
       int elem = tab[i];
       for (j = i; j > 0 && tab[j-1] >= elem; j--)
           tab[j] = tab[j-1];
       tab[j] = elem;
   }
}

Je suis intéressé par les commentaires, et je remercie les efforts de candide et yoch, sans qui cette amélioration aurait sans doute attendu un an ou deux (en me mettant la honte sur le forum, on arrive parfois à me forcer à faire des choses qui ne me motivent pas du tout).

Au passage, quand la version du tutoriel vous ira (ce qui sera, je l'espère, bientôt), je vous invite à rajouter un petit edit sur ces posts d'anthologie que tu cites pour préciser que le tutoriel a été corrigé (grâce à vous).

GurneyH > on peut très bien avoir des boucles for dans des fonctions récursives, et tes mesures de performances n'ont pas de sens tant que tu ne les fais pas en -O2 au moins (en dessous gcc n'optimise pas les appels terminaux). Si tu mets les options d'optimisations nécessaires, tu réaliseras certainement que la version récursive est aussi performante qu'une version itérative correspondante.

elmcherqui

2 janvier 2010 à 1:23:10

Citation : GurneyH

@Alienore: une boucle for dans une fonction récursive.

ta remarque me surprend beaucoup vu les liens que tu propose dans ta signature o_O

candide

2 janvier 2010 à 1:28:09

Citation : bluestorm

void tri_insertion(int tab[], int taille)
{
   int i, j;
   for (i = 1; i < taille; ++i) {
       int elem = tab[i];
       for (j = i; j > 0 && tab[j-1] >= elem; j--)
           tab[j] = tab[j-1];
       tab[j] = elem;
   }
}

Juste deux choses qui me gênent :

1°) le fait que s'il n'y a pas de décalage (et donc pas d'insertion à faire), l'élément t[i] est échangé avec lui-même (ligne 8);

2°) le supérieur ou égal au lieu d'un supérieur strict (ligne 6) qui peut engendrer un ou plusieurs décalages inutiles (imagine un tableau qui n'est constitué que d'une seule valeur). Mais peut-être que le >= a par ailleurs un avantage que je n'ai pas vu.

Citation : bluestorm

Au passage, quand la version du tutoriel vous ira (ce qui sera, je l'espère, bientôt), je vous invite à rajouter un petit edit sur ces posts d'anthologie que tu cites pour préciser que le tutoriel a été corrigé (grâce à vous).

Arthurus

2 janvier 2010 à 1:29:52

Citation : elmcherqui

EDIT : @ arthurus ta fonction est erronee regarde ton entree et ta sortie , sinon ben il est a moitié recursif donc c'est nomal qu'il ne puise pas la pile plus vite .

Mais de quoi tu parles ????
Je n'ai pas publié de code moi !!

elmcherqui

2 janvier 2010 à 1:38:16

Citation : Arthurus

Citation : elmcherqui

EDIT : @ arthurus ta fonction est erronee regarde ton entree et ta sortie , sinon ben il est a moitié recursif donc c'est nomal qu'il ne puise pas la pile plus vite .

Mais de quoi tu parles ????
Je n'ai pas publié de code moi !!

wooops , tu a cité aliennore , je croyais que c'etais toi qui a publie le code

, désolé ,j'edite mon post tisuite !

bluestorm

2 janvier 2010 à 9:46:03

Citation

1°) le fait que s'il n'y a pas de décalage (et donc pas d'insertion à faire), l'élément t[i] est échangé avec lui-même (ligne 8);

Je ne compte pas changer ça : c'est une propriété de régularité (ça marche même dans le cas particulier où ..) qui simplifie le code sans changer significativement les performances. Je préfère sacrifier N échanges et gagner en simplicité : un branchement conditionnel de plus ça se ressent fortement chez les débutants qui n'ont pas l'habitude d'envisager le code dans son ensemble.

Pour le >=, tu as tout à fait raison, j'avais fait attention dans une version précédente du code mais ça a sauté. Je corrige.

candide

2 janvier 2010 à 10:09:31

Citation : bluestorm

c'est une propriété de régularité (ça marche même dans le cas particulier où ..)

Comprends pas ce que tu veux dire par là.

Citation : bluestorm

qui simplifie le code sans changer significativement les performances.

Sans doute mais je trouve quand même absurde de se retrouver à remplacer 42 par 42 (en moyenne ça devrait être une fois sur deux et même à chaque fois si tu prends une suite déjà triée).

Citation : bluestorm

Je préfère sacrifier N échanges et gagner en simplicité : un branchement conditionnel de plus ça se ressent fortement chez les débutants qui n'ont pas l'habitude d'envisager le code dans son ensemble.

C'est un argument acceptable mais je pense qu'il faut quand même prendre soin de préciser que c'est un choix.

Je pense que le code ci-dessous n'effectue aucune redondance (pas d'auto-affectation, pas de répétition de comparaison). Mais effectivement, ça alourdit un peu le code.

#include <stdio.h>

void tri_insertion(int tab[], int taille)
{
  int i, j;

  for (i = 1; i < taille; ++i)
    {
      int elem = tab[i];

      if (tab[i] < tab[i - 1])
        {                       /* Il y aura insertion (et aussi décalage) */
          /* Premier décalage */
          tab[i] = tab[i - 1];
          /* On cherche où on doit se faire l'insertion */
          for (j = i - 1; j > 0 && tab[j - 1] > elem; j--)
            /* On décale en même temps */
            tab[j] = tab[j - 1];

          /* L'insertion */
          tab[j] = elem;
        }
    }
}

int main(void)
{
  int tab[] = { 42, 21, 42, 19, 31 };
  int n = sizeof tab / sizeof *tab;
  int i;

  tri_insertion(tab, n);

  for (i = 0; i < n; i++)
    printf("%d ", tab[i]);
  puts("");
  return 0;
}

19 21 31 42 42

bluestorm

2 janvier 2010 à 11:58:42

Citation : candide

Citation : bluestorm

c'est une propriété de régularité (ça marche même dans le cas particulier où ..)

Comprends pas ce que tu veux dire par là.

Je veux dire que souvent, quand les algorithmes sont solides, un code simple pour faire fonctionner l'algorithme dans le cas général fonctionne aussi pour le cas particulier, "par hasard", mais ce n'est pas par hasard, c'est une confirmation de la solidité de l'algorithme.

Un exemple assez classique :

int somme(int tab[], int taillle)
{
   int i, res = 0;
   for (i = 0; i < taille; ++i)
     res += tab[i];
   return res;
}

Ce code fonctionne même dans le cas où taille vaut 0. Au contraire, un code "plus astucieux" qui fait l'initialisation res = tab[0] et i = 1 demandera un test supplémentaire pour être correct dans tous les cas. Ici, la solidité vient du fait qu'on reproduit la méthode utilisée en mathématiques pour définir les produits n-aires, qui a fait ces preuves dans cette vielle discipline où la simplicité est mise en avant.

L'autre version effectue une addition de moins, mais reste plus désagréable à coder et moins élégante (sachant qu'avec les processeurs actuels, il n'est pas certain qu'elle soit plus rapide en pratique, vu les machins de prédiction de branchement etc.). L'utiliser en pratique pourquoi pas, mais à mon avis dans un tutoriel il faut favoriser la clarté.

De plus, avec les processeurs modernes, il n'est pas certain qu'ajouter un test pour prendre en compte un cas particulier apporte effectivement de meilleurs performances : une erreur de prédiction de branchement peut coûter bien plus cher qu'un échange tableau-registre-tableau quand le tableau est déjà en cache (mais je pense qu'en pratique les tests du type "si taille = 0" sont bien prédits par l'heuristique du processeur).

Edit :
J'ai fait des tests, et la version que tu proposes est systématiquement un peu plus lente (j'ai surtout testé en -O2/O3, mais il me semble que c'est aussi le cas sans optimisations) que le code donné dans le tutoriel pour un tableau tiré au hasard : pour 70000 éléments en O3, c'est environ 3.7s pour la version de candide et 3.5s pour la mienne. Ci-dessous le code de test :

#include <stdio.h>
#include <stdlib.h>

void blue_insertion(int tab[], int taille)
{
   int i, j;
   for (i = 1; i < taille; ++i) {
       int elem = tab[i];
       for (j = i; j > 0 && tab[j-1] >= elem; j--)
           tab[j] = tab[j-1];
       tab[j] = elem;
   }
}

void candide_insertion(int tab[], int taille)
{
  int i, j;

  for (i = 1; i < taille; ++i)
    {
      int elem = tab[i];

      if (tab[i] < tab[i - 1])
        {                       /* Il y aura insertion (et aussi décalage) */
          /* Premier décalage */
          tab[i] = tab[i - 1];
          /* On cherche où on doit se faire l'insertion */
          for (j = i - 1; j > 0 && tab[j - 1] > elem; j--)
            /* On décale en même temps */
            tab[j] = tab[j - 1];

          /* L'insertion */
          tab[j] = elem;
        }
    }
}


int main(void)
{
    int i, n, *tab;

    scanf("%d", &n);
    tab = malloc(n * sizeof(int));
    for (i = 0; i < n; ++i)
        tab[i] = rand();

    #ifndef CANDIDE
    printf("blue\n");
    blue_insertion(tab, n);
    #else
    printf("candide\n");
    candide_insertion(tab, n);
    #endif
    
    #ifdef PRINT
    for (i = 0; i < n; ++i)
        printf("%d\t", tab[i]);
    #endif

    return 0;
}

Citation : candide

Citation : bluestorm

qui simplifie le code sans changer significativement les performances.

Sans doute mais je trouve quand même absurde de se retrouver à remplacer 42 par 42 (en moyenne ça devrait être une fois sur deux et même à chaque fois si tu prends une suite déjà triée).

Non, ce n'est pas une fois sur deux en moyenne : ça n'arrive que quand l'élément est supérieur à tous les précédents, donc, si l'on suppose un tirage uniforme et indépendant des valeurs du tableau, ça se produit avec une probabilité <math>\(2^{-i}\)</math> au rang <math>\(i\)</math> (intersection de <math>\(i\)</math> évènements indépendants de probabilité <math>\(1/2\)</math>), soit en moyenne entre une et deux fois au total sur l'ensemble du tableau, quelle que soit sa taille.

Edit : Bien sûr, les données des applications sont rarement uniformes et indépendantes. En pratique, il est raisonnable de supposer que les tableaux produits par l'activité humaine auront plutôt tendance à être un peu triés en général, donc il y aurait plus d'échanges à vide que le prédit le modèle moyen uniforme. En particulier, dans les cas où on utilise un tri par insertion pour "finir" des tableaux semi-triés par des méthodes plus rapides sur de gros ensembles, le comportement sur des tableaux presque-triés est important.

Edit : J'ai reproduit les tests pratiques dans le cas d'un tableau déjà trié (<minicode>tab[i] = i<minicode>), et la version simple reste plus performante (2.15s contre 2.60s, sur 20 000 itérations sur un tableau de taille 20 000).
Je dois dire que je suis un peu surpris par ces résultats, mais comme je le disais plus haut la micro-optimisation sur les processeurs est quelque chose de très difficile, qui moi me dépasse en tout cas.

Citation

C'est un argument acceptable mais je pense qu'il faut quand même prendre soin de préciser que c'est un choix.

Si tu insistes, je le mentionnerai dans le tutoriel, mais seulement accessoirement.

1 2 >>