Discussion :

[siham-gh]

Salut à tous

j'ai un problème de calculer le temps d’exécution d'un algorithme de trier un tableau par la méthode de trier rapide

Voici le code

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
 
 
#include <time.h>
 
 int partitionner(int *tableau, int p, int r) {
 
    int pivot = tableau[p], i = p-1, j = r+1;  int temp;
 
    while (1) {
        do
            j--;
        while (tableau[j] > pivot);
        do
            i++;
        while (tableau[i] < pivot);
        if (i < j) {
            temp = tableau[i];
            tableau[i] = tableau[j];
            tableau[j] = temp;
        }
        else
            return j;
 
 
             }
                   }
 
void quickSort (int *tableau, int p, int r) {
    int q;
    if (p < r) {
        q = partitionner(tableau, p, r);
        quickSort(tableau, p, q);
        quickSort(tableau, q+1, r);
    }
}
 
 
 
 
 
main(){  int i,n;       int tmp,j,c;    float temps;
 
 
 
    clock_t t1, t2;
 
       tableau =(int*)malloc((n)*sizeof(int));
 
 
      printf("introduire  la taille de tableau   =\n\n");
      scanf("%d",&n);
 
  for(i=1;i<=n;i++)
 
              {          printf("tableau[%d]=",i);
                         scanf("%d",&tableau[i]);
              }
 
                                          t1 = clock();
 
 
                          quickSort(tableau, 1,n) ;
 
            t2 = clock();
 
 
    temps = (float)(t2-t1)/CLOCKS_PER_SEC;
 
    printf("temps d'execution = %f\n", temps);
 
     printf("\n La complexité d'algorithme de trier rapide est %f",n*log (n));
 
 
      }

je vais calculer seulement le procédure de trier pas les saisies de tableau

( le procédure de trier récursif)
merci

[Flow_75]

Tu as quoi comme probleme ?

[siham-gh]

Ou je mettre les instructions de calculs les temps d’exécution dans le programme principale ou dans le procédure et le temps retournées (temps) en secondes ou microsecondes

[Flow_75]

Ou je mettre les instructions de calculs les temps d’exécution dans le programme principale ou dans le procédure et le temps retournées (temps) en secondes ou microsecondes

Tu as testé le programme au moins ?
Le code a l'air bon...

[siham-gh]

Bien sur je teste


Ou le mettre

t1 = clock();

et Ou le mettre

t2 = clock();

[edgarjacobs]

Hello,

Je n'ai fait que survoler l'algorithme de tri, qui a l'air juste.

Pour calculer le temps, c'est bien là où tu les as mis: t1 juste avant l'appel, t2 juste après.
t2-t1 te donnera alors le temps passé à trier les éléments.

Edgar.

[Neckara]

t2-t1 te donnera alors le temps passé à trier les éléments.

Faux, t2-t1 te donneras le temps passé à trier les éléments ET le temps que le processus a dû attendre pour avoir accès au processeur.

Donc si tu fait le test en ayant lancé plein de processus actif, tu auras une grande différence de résultat si tu faisais le test avec très peu de processus actif.
Sous Linux, il existe la commande time qui permet d'avoir ces différents temps (temps total, temps utilisateur, temps système). De là, tu peux faire plusieurs essais sur ton programme complet puis en faire de même sur un autre programme qui cette fois ne n'exécutera que les fonctions situées avant et après le trie. Tu pourras alors soustraire les résultats pour obtenir un temps assez précis.

[siham-gh]

Faux, t2-t1 te donneras le temps passé à trier les éléments ET le temps que le processus a dû attendre pour avoir accès au processeur.

Donc si tu fait le test en ayant lancé plein de processus actif, tu auras une grande différence de résultat si tu faisais le test avec très peu de processus actif.
Sous Linux, il existe la commande time qui permet d'avoir ces différents temps (temps total, temps utilisateur, temps système). De là, tu peux faire plusieurs essais sur ton programme complet puis en faire de même sur un autre programme qui cette fois ne n'exécutera que les fonctions situées avant et après le trie. Tu pourras alors soustraire les résultats pour obtenir un temps assez précis.

Moi aussi je cherche seulement le temps d’exécution de trie les elements

[Bktero]

Il y a déjà eu des discussions sur ce thème dans le forum C. La fonction recherche t'aidera à les retrouver. Le bilan des discussions étaient que tu ne pourras pas avoir exactement le temps d'exécution de ton algorithme de manière simple.

Voir notamment :

http://www.developpez.net/forums/d11...on-algorithme/