Citation : bluestorm

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.

Oui, mais je ne vois pas vraiment le rapport avec ton code (sauf que tu affectes une valeur à elle-même et donc que tout se passe bien).

Citation : bluestorm

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)

Oui, je m'y attendais, les branchements comme ça dans les boucles sont couteux.

Citation : bluestorm

Non, ce n'est pas une fois sur deux en moyenne

Ah oui, tu as raison, c'est effectivement très très peu en moyenne et cela justifie parfaitement ta méthode.

Le seul truc qui me gêne (mais un tout petit peu) c'est que ça fait toujours bizarre d'auto-affecter une valeur. Quand on trie ses cartes, on ne fait jamais ça (sortir une carte pour la remettre à la même place) et je trouve que la métaphore du tri de cartes est très utile ici pour coder le tri par insertion.

De toute façon, même le décalage n'a pas lieu avec de vraies cartes : l'insertion se fait "en place" (bon physiquement si on tient fort dans la main, ça bouge un peu), le décalage est un artefact de la structure de donnée utilisée : un tableau, qui ne permet pas d'insertion en temps constant.

Je pense que le code est plus naturel quand on utilise une liste chaînée, en tout cas qu'il ressemble plus à l'idée qu'on s'en fait en pensant aux cartes. Cf. mon tuto en OCaml.

Citation : bluestorm

De toute façon, même le décalage n'a pas lieu avec de vraies cartes : l'insertion se fait "en place" (bon physiquement si on tient fort dans la main, ça bouge un peu), le décalage est un artefact de la structure de donnée utilisée : un tableau, qui ne permet pas d'insertion en temps constant.

Je pense que le code est plus naturel quand on utilise une liste chaînée, en tout cas qu'il ressemble plus à l'idée qu'on s'en fait en pensant aux cartes.

Tout à fait.

bluestorm et candide, merci c'est très intéressant...
Même sur un tri de ce type il y a des questions à soulever!

Citation : elmcherqui

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

Peux tu préciser ce qui te surprends, stp.
A la limite, si on souhaite montrer un exemple récursif, on montre un exemple... récursif,! Surement pas avec une boucle dans une fonction, c'est aussi simple que ça...

J'ai fait des tests avec ton code bluestorm et chez moi que ce soit en -O2 ou -O3 les temps entre ton code et celui de candide restent les même
J'ai fait des tests avec de très grands tableaux pour voir si il y avait un écart et même avec des tableaux de 500 000 éléments ça ne change rien vos 2 codes me sortent le même temps

@ GurneyH : Un exemple de fonction récursive qui utilise des boucles for : L'algo min/max

Citation : Pouet_forever

J'ai fait des tests avec ton code bluestorm et chez moi que ce soit en -O2 ou -O3 les temps entre ton code et celui de candide restent les même
J'ai fait des tests avec de très grands tableaux pour voir si il y avait un écart et même avec des tableaux de 500 000 éléments ça ne change rien vos 2 codes me sortent le même temps

@ GurneyH : Un exemple de fonction récursive qui utilise des boucles for : L'algo min/max

Hum, que tu peux certainement implémenter sans boucles, ou sans récursivité...

Oui sûrement, mais c'est (je pense) plus simple de le faire de manière récursive et avec des boucles
Après il y a des centaines de manières de coder la même chose, et chacun à sa préférence

@ gurney : je veux simplement dire que pour concevoir des algorithmes meme recursif , on peut souvent allier recursif et iteratif , et pas si il est recursif qu'il l'est exlusivement . c'est tous .

Je ne vois pas ce qu'il y a de choquant dans le fait que j'ai utilisé une boucle for dans une fonction récursive. On m'a demandé de faire une méthode de tri par insertion comme je l'avais dit, c'est-à-dire de se dire qu'on sait que les n premiers éléments sont triés et qu'on ajoute le suivant. S'il n'y a qu'un élément, le tableau est trié.
Je n'ai jamais parlé de récursivité pour aller mettre l'élément courant en place.

Personnellement, je trouve idiot de faire soit tout itératif soit tout récursif, d'autant plus que si on va par là, dès qu'on fait une fonction récursive, on s'interdirait l'emploi de toute fonction itérative parce qu'on fait du récursif ?
Pour moi, le récursif est une manière de voir les choses alors que l'itératif en est une autre. Il y a autant de boucles dans les 2 codes que j'ai proposés (1 boucle for et 1 due à la récursivité pour la première tandis que la seconde se contente de 2 boucles for).

Ne tirez pas...

C'est simplement, que ça m'a fait marrer de voir une boucle dans ton tri récursif...
Je trouve ça maladroit(apparemment je suis le seul. )

Le but n'était en tout cas pas de te vexer.

///permet de placer l'élément d'indice n du tableau tab à sa place en supposant que les n-1 premiers éléments du tableau sont triés
void reculer_n(int tab[], int n)
{
  int tmp = tab[n];
  int i;
  for(i = n - 1;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;
}

///prend un tableau et sa taille pour le trier du plus petit au plus grand
void tri_insert_rec(int* tab, int taille)
{
  ///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
  reculer_n(tab,taille-1);
}

Tu préfères une fonction récursive comme ça ?

Sinon, en récursif complet :

void reculer_n(int tab[], int n, int elt)
{
  if(tab[n] > elt)
  {
    tab[n+1] = tab[n];
    reculer_n(tab,n-1,elt);
  }
  else
    tab[n] = elt;
}

///prend un tableau et sa taille pour le trier du plus petit au plus grand
void tri_insert_rec(int* tab, int taille)
{
  ///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
  reculer_n(tab,taille-2,tab[taille-1]);
}

@Alienore:
Il sont particuliers tes tris.

Tableau avant tri.
88
31719
21027
26723
16311
31923
2375
13221
13354
9201

Test...
Tableau (presque) trie en 0.000000 s :
9201
13354
31923
31923
31923
26723
31719
31719
31719
31923


Process returned 0 (0x0)   execution time : 0.031 s
Press any key to continue.