Discussion :

[Hezoq]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[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

[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]

[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.

[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?

[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.

[muad'dib]

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)

[Garulfo]

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

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.

[DaZumba]

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:

If you know what bubble sort is, wipe it from your mind; if you don't, make a point of never finding out!

[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)

[Emmanuel Delahaye]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}