Gné ?!? cherche explications

Version imprimable

Voilà, je me demande vraiment pourquoi avec le code source ci dessous j'optiens des résultats aussi incohérents :
Code:

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 const int N= 50000; int i,j; void tri_bulle(int *tab/*,const int A*/){ int aux,a,b; a=clock(); b=0; for (i=N-1;i>0;i--){ for (j=1;j<=i;j++){ if (tab[j-1]>tab[j]){ aux=tab[j-1];tab[j-1]=tab[j];tab[j]=aux; //b=1; } } //if (b==0) i=0; } b=clock(); a=b - a; printf("par bulle : %d\n",a); fflush(stdout); } void inversion(int tab[N]){ for (i=0;i<N;i++){ j=tab[N-i];tab[N-i]=tab[i];tab[i]=j; } int main(){ int tab[N]; srand(time(NULL)); rand(); saisie(tab); tri_bulle(tab); inversion(tab); tri_bulle(tab); tri_bulle(tab); return 0; }
j'obtiens les temps suivant :
par bulle : 18750
par bulle : 7625
par bulle : 7703

le truc c'est pourquoi le programme met moins de temps à inverser un tableau qu'à seulement le parcourir ?

21/05/2007, 17h21
straasha

t'es sur que ton prog marche bien deja ?
parce dans inversion pour i==0 tu accede a tab[N] qui est hors tableau...
en plus c'est pas jusqu'a N que i doit aller mais jusqu'a N/2 sinon tu inverse 2 fois et tu te retrouve avec le meme tableau
21/05/2007, 17h25
straasha

et quand tu inverse juste le tableau, tu ne calcule pas le temps donc comment tu fais pour savoir que c'est plus lent ?
[edit]
je viens de comprendre, le 2e tri_bulle fait l'inversion, et le 3e ne doit rien faire puisque c'est deja trie ;)
donc voir mon post precedent pour ton erreur
[/edit]
21/05/2007, 17h46
Hezoq

Nan je suis certain du code : c'est pour des TP qu'on fait ça et même le prof bloque sur l'explication du phénomène.
21/05/2007, 18h03
Jean-Marc.Bourguet

1/ le code que tu montres n'effectue pas d'inversion, donc tu fais deux fois rien du tout
2/ as-tu verifie quel etait l'increment minimal de clock sur ta machine?
3/ et le prof apprecie comment les variables globales n'ayant qu'un usage local?
21/05/2007, 18h16
straasha

je persiste a dire que inverser tab[i] et tab[N-1-i] c'est la meme chose qu'inverser tab[N-1-i] et tab[i]
donc si tu parcours le tableau pour i de 0 a N-1 tu inversera 2 x chaque case donc ton tableau final sera le meme qu'au debut.
21/05/2007, 18h23
muad'dib

Citation:

Envoyé par Hezoq

Nan je suis certain du code : c'est pour des TP qu'on fait ça et même le prof bloque sur l'explication du phénomène.

Les profs sont loin d'être des bibles de la programmation la plupart du temps ... (pardon aux profs compétents qui me liront)

Citation:

Envoyé par Hezoq

Voilà, je me demande vraiment pourquoi avec le code source ci dessous j'optiens des résultats aussi incohérents :
<...>
le truc c'est pourquoi le programme met moins de temps à inverser un tableau qu'à seulement le parcourir ?

Dejà, il faudrait travailler sur du code lisible et un algorithme correct. Ensuite, il suffit de poser quelques traces pour comprendre ce qui se passe :

Code:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
swap_i (int *a, int *b)
{
   int t = *a;
   *a = *b;
   *b = t;
}
 
/* http://en.wikipedia.org/wiki/Bubble_sort */
void tri_bulle (int *tab, int n)
{
   int a = clock ();
   int swapped;
   unsigned long count = 0;
   printf ("tri en cours ...");
   fflush (stdout);
   do
   {
      int i;
      swapped = 0;
      n--;
      for (i = 0; i < n; i++)
      {
         if (tab[i] > tab[i + 1])
         {
            swap_i (tab + i, tab + i + 1);
            swapped = 1;
            count++;
         }
      }
   }
   while (swapped);
 
   printf ("\rtri bulle : %ld (%lu swap%s)\n", clock () - a, count,
           count > 1 ? "s" : "");
}
 
void inversion (int tab[], int n)
{
   int i;
   for (i = 0; i < n - 1; i++)
   {
      swap_i (tab + i, tab + i + 1);
   }
}
 
void init (int tab[], int n)
{
   int i;
   for (i = 0; i < n; i++)
   {
      tab[i] = (rand () / (double) RAND_MAX) * 100;
   }
}
 
void aff (int const tab[], int n)
{
   int i;
   for (i = 0; i < n; i++)
   {
      printf ("%4d", tab[i]);
   }
}
 
int main (void)
{
#define N 50000
 
   static int tab[N];
   srand (time (NULL));
   rand ();
   init (tab, N);
   aff (tab, 20);
   tri_bulle (tab, N);
   aff (tab, 20);
   inversion (tab, N);
   aff (tab, 20);
   tri_bulle (tab, N);
   aff (tab, 20);
   tri_bulle (tab, N);
   aff (tab, 20);
   return 0;
}

21/05/2007, 19h49
Garulfo

Citation:

Envoyé par Hezoq

Nan je suis certain du code : c'est pour des TP qu'on fait ça et même le prof bloque sur l'explication du phénomène.

Je parle d'expérience: le prof n'est pas dieu et ne peut pas trouver automatiquement les erreurs ;)

Autre chose, en informatique, tu ne peux être certain du code.
Et si ça ne marche pas, c'est que ton code n'est pas bon :mrgreen:

Finalement... ta question, « pourquoi le programme met moins de temps à inverser un tableau qu'à seulement le parcourir ? » n'est pas assez précise.
Veux tu dire pourquoi il met moins de temps à inverser plutôt qu'à trier ?
Tu ne calcules pas le temps de l'inversion. Sur quoi te bases tu ?

Mais bon si c'est ça, tu as une simple boucle pour l'inversion (complexité linéaire) et une double pour le tri (complexité quadratique). Il est donc normal que l'inversion soit plus rapide que le tri.
21/05/2007, 23h30
DaZumba

Citation:

Envoyé par Hezoq

Nan je suis certain du code : c'est pour des TP qu'on fait ça et même le prof bloque sur l'explication du phénomène.

Hmm. Un prof qui enseigne le tri à bulle (bubble sort), c'est un peu inquiétant. Les auteurs des Numerical Recipes sont très clairs au sujet de cet algorithme:

Citation:

Envoyé par Numerical Recipes Section 8.0

If you know what bubble sort is, wipe it from your mind; if you don't, make a point of never finding out!
22/05/2007, 23h26
Hezoq

je vous remercie tous grandement de vos réponses, mais j'ai plusieurs remarques à faire sur celle-ci :

1er : effectivement si mon algo d'inversion n'inversait pas, j'obtenait logiquement des résultats incohérents (ça m'apprendra à pas vérifier chacun de mes algos)
2nd : le prof n'est effectivement pas une bible ni dieu, mais il est un jeune enseignant qui sort tout juste de mon école (le programme scolaire est donc encore frais dans sa tete).
3me : c'est pas qu'on aprends le bubble sort en particulier, c'est qu'on le vois parmis d'autre afin d'étudier parallèlement la complexité des algos. (personnellemet, des algos de tri qu'on a vu mon préféré est le merge sort)
23/05/2007, 09h19
Emmanuel Delahaye

Citation:

Envoyé par Hezoq

ds le bubble sort en particulier, c'est qu'on le vois parmis d'autre afin d'étudier parallèlement la complexité des algos. (personnellemet, des algos de tri qu'on a vu mon préféré est le merge sort)

Un petit site qui m'amuse toujours :

http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html