Tri a bulles

**GyZmoO** · 20/06/2007, 11h21

Bonjour a tous ! Je me sers de cette fonction :

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
 
void triBulle(double * t, int taille)
{
 
    int i = 0; /* Indice de répétition du tri */
    int j = 0; /* Variable de boucle */
    double tmp = 0; /* Variable de stockage temporaire */
 
    /* Booléen marquant l'arrêt du tri si le tableau est ordonné */
    int en_desordre = TRUE;
 
    /* Boucle de répétition du tri et le test qui
       arrête le tri dès que le tableau est ordonné */
    for(i = 0 ; (i < taille) && en_desordre; i++)
    {
        /* Supposons le tableau ordonné */
        en_desordre = FALSE;
 
        /* Vérification des éléments des places j et j-1 */
        for(j = 1 ; j < taille - i ; j++)
        {
            /* Si les 2 éléments sont mal triés */
            if(t[j] < t[j-1])
            {
                /* Inversion des 2 éléments */
                tmp = t[j-1];
                t[j-1] = t[j];
                t[j] = tmp;
 
                /* Le tableau n'est toujours pas trié */
                en_desordre = TRUE;
            }
        }
    }
}

pour trier un tableau de double. Mais j'ai toujours un soucis, systématiquement, quand j'affiche toutes les cases du tableau (y'en a 150 pour info), et ben la plus grosse valeur est dans la première case, et à partir de la 2nd case, tout est bien classé par ordre croissant !!!!!! Et evidemment ça fausse mes résultats !

**Médinoc** · 20/06/2007, 11h38

Code :

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

for(j = 1 ; j < taille - i ; j++)

J'ai des doutes sur "taille-i"...

D'ailleurs, il me semble que le tri à bulles fait deux boucles imbriquées complètes, contrairement à d'autres tris en O(n²) comme le tri par sélection...

**GyZmoO** · 20/06/2007, 11h45

Je t'avouerais que j'ai pris le code tout pret sur le net, sur wikipédia... Donc tu penses que c'est le tri qui déconne?

**GyZmoO** · 20/06/2007, 12h26

Bon bah j'ai pris une fonction de tri rapide :

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
 
void echange (double *tab, int i, int j)
{
    double tampon = tab[i];
 
    printf("Fonction echange appellee \n");
    fflush(stdout);
 
    tab[i] = tab[j];
    tab[j] = tampon;
}
 
void triRapide (double *tab, int G, int D)
{
    int g, d;
    double val;
 
    printf("triRapide bien appellée \n");
    fflush(stdout);
 
    if (D <= G)
    {
        return;
    }
 
    printf("premier if passe \n");
    fflush(stdout);
 
    val = tab[D];
    g = G;
    d = D - 1;
    do
    {
        while ((tab[g] <= val))
        {
 
            printf("g ++ \n");
            fflush(stdout);
            g++;
        }
        while ((tab[d] > val) && (d>G))
        {
              printf("d ++ \n");
            fflush(stdout);
            d--;
        }
        if (g < d)
        {
            echange (tab, g, d);
        }
    }
    while (g < d);
 
    printf("J'appelle echange \n");
    fflush(stdout);
 
    echange (tab, g, D);
    triRapide (tab, G, g - 1);
    triRapide (tab, g + 1, D);
}

Toujours la même bizarrerie, quand j'affiche les cases de mon tableau

T[0] = 1,33
T[1] = 0,38
T[2] = 0,39
T[3] = 0,41 .. .

Aprés la première case tout est bien classé, mais y'a toujours cette valeur bizarre qui est dans la première case . . . Vous avez une idée ??

**Franck.H** · 20/06/2007, 12h52

Faut regarder dans la page Sources C, il y'a des choses qui peuvent servir: Tri à bulle

**GyZmoO** · 20/06/2007, 13h03

Yep merci, j'ai déja pris :

- le tri a bulle
- le tri rapide
- le tri par maximum
- et le tri par minimum ici sur les pages sources.

MAIS, j'ai toujours la première case qui merde !!!

VALEUR DU TABLEAU SPAM = 1.333333
VALEUR DU TABLEAU SPAM = 0.386792
VALEUR DU TABLEAU SPAM = 0.395349
VALEUR DU TABLEAU SPAM = 0.398148
VALEUR DU TABLEAU SPAM = 0.409091
VALEUR DU TABLEAU SPAM = 0.409091
VALEUR DU TABLEAU SPAM = 0.409091
VALEUR DU TABLEAU SPAM = 0.414414
VALEUR DU TABLEAU SPAM = 0.414414
VALEUR DU TABLEAU SPAM = 0.419643
VALEUR DU TABLEAU SPAM = 0.419643
VALEUR DU TABLEAU SPAM = 0.419643
VALEUR DU TABLEAU SPAM = 0.419643
VALEUR DU TABLEAU SPAM = 0.419643
VALEUR DU TABLEAU SPAM = 0.422222
VALEUR DU TABLEAU SPAM = 0.422222
VALEUR DU TABLEAU SPAM = 0.424779
VALEUR DU TABLEAU SPAM = 0.427313
VALEUR DU TABLEAU SPAM = 0.427313
VALEUR DU TABLEAU SPAM = 0.432314
VALEUR DU TABLEAU SPAM = 0.432314
VALEUR DU TABLEAU SPAM = 0.432314
VALEUR DU TABLEAU SPAM = 0.437229
VALEUR DU TABLEAU SPAM = 0.437229
VALEUR DU TABLEAU SPAM = 0.437229
VALEUR DU TABLEAU SPAM = 0.437229
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.439655
VALEUR DU TABLEAU SPAM = 0.442060
VALEUR DU TABLEAU SPAM = 0.442060
VALEUR DU TABLEAU SPAM = 0.442060
VALEUR DU TABLEAU SPAM = 0.444444
VALEUR DU TABLEAU SPAM = 0.444444
VALEUR DU TABLEAU SPAM = 0.444444
VALEUR DU TABLEAU SPAM = 0.444444
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.446809
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.449153
VALEUR DU TABLEAU SPAM = 0.451327
VALEUR DU TABLEAU SPAM = 0.451477
VALEUR DU TABLEAU SPAM = 0.451477
VALEUR DU TABLEAU SPAM = 0.451477
VALEUR DU TABLEAU SPAM = 0.451477
VALEUR DU TABLEAU SPAM = 0.451477
VALEUR DU TABLEAU SPAM = 0.451477
VALEUR DU TABLEAU SPAM = 0.453782
VALEUR DU TABLEAU SPAM = 0.453782
VALEUR DU TABLEAU SPAM = 0.456067
VALEUR DU TABLEAU SPAM = 0.456067
VALEUR DU TABLEAU SPAM = 0.456067
VALEUR DU TABLEAU SPAM = 0.456067
VALEUR DU TABLEAU SPAM = 0.458333
VALEUR DU TABLEAU SPAM = 0.846154
VALEUR DU TABLEAU SPAM = 0.846154
VALEUR DU TABLEAU SPAM = 0.846154
VALEUR DU TABLEAU SPAM = 0.846154
VALEUR DU TABLEAU SPAM = 0.848485
VALEUR DU TABLEAU SPAM = 0.853846
VALEUR DU TABLEAU SPAM = 0.853846
VALEUR DU TABLEAU SPAM = 0.853846
VALEUR DU TABLEAU SPAM = 0.853846
VALEUR DU TABLEAU SPAM = 0.853846
VALEUR DU TABLEAU SPAM = 0.853846
VALEUR DU TABLEAU SPAM = 0.861538
VALEUR DU TABLEAU SPAM = 0.861538
VALEUR DU TABLEAU SPAM = 0.861538
VALEUR DU TABLEAU SPAM = 0.869231
VALEUR DU TABLEAU SPAM = 0.869231
VALEUR DU TABLEAU SPAM = 0.869231
VALEUR DU TABLEAU SPAM = 0.870370
VALEUR DU TABLEAU SPAM = 0.876923
VALEUR DU TABLEAU SPAM = 0.876923
VALEUR DU TABLEAU SPAM = 0.876923
VALEUR DU TABLEAU SPAM = 0.880000
VALEUR DU TABLEAU SPAM = 0.892308
VALEUR DU TABLEAU SPAM = 0.907692
VALEUR DU TABLEAU SPAM = 0.907692
VALEUR DU TABLEAU SPAM = 0.953846
VALEUR DU TABLEAU SPAM = 0.969231
VALEUR DU TABLEAU SPAM = 1.061538
VALEUR DU TABLEAU SPAM = 1.100000

Voici ce que j'obtiens . . . je comprend vraiment pas pourquoi . .. c'est à devenir fou

**droggo** · 20/06/2007, 13h22

Jao,

Montre-nous tout ton code, car au moins ton tri à bulles est correct.

**GyZmoO** · 20/06/2007, 14h00

Mon code est qd même conséquent, je vais mettre le bout de code qui correspond au remplissage du tableau :

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
 
 
int main()
...
 
    double *resultatsSpam;
    double *resultatsNotSpam;
 
...
    resultatsSpam = malloc(sizeof(double) * NB_TEMOINS);
    resultatsNotSpam = malloc(sizeof(double) * NB_TEMOINS);
 
    if ((resultatsSpam == NULL) || (resultatsNotSpam == NULL))
    {
        perror("main : Erreur allocation tableaux résultats ! \n");
        return ECHEC_ALLOC;
    }
....
 
resultatsNotSpam[cpt] = kolmo(lectureMail->d_name, lectureTemoinNotSpam->d_name, NOTSPAM,
                                                  adrMailString, adrTemoinSpamString, adrTemoinNotSpamString);
 
...
 
resultatsSpam[cpt] = kolmo(lectureMail->d_name, lectureTemoinSpam->d_name, SPAM,
                                               adrMailString, adrTemoinSpamString, adrTemoinNotSpamString);

aprés voici ma fonction kolmo :

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
 
double kolmo(char *f1, char *f2, int x, char * pathRepMail, char * pathRepSpam, char * pathRepNotSpam)
{
    FILE *file1;
    FILE *file2;
    FILE *concat;
 
    int res;
    long tailleA;
    long tailleB;
    long tailleAB;
 
 
    char final[200];
 
 
    /* On compresse avec la méthode LZW */
    printf("--- Fichiers analysés ---\n");
    fflush(stdout);
    printf("--- f1 : %s ---\n", f1);
    fflush(stdout);
    printf("--- f2 : %s ---\n", f2);
    fflush(stdout);
 
    sprintf(final, "%s%s", pathRepMail, f1);
 
    res = LZW(final, "tmp1");
 
    if (res < 0)
    {
        perror("kolmo : La compression a échouée ! \n");
        return ECHEC_COMPRESSION;
    }
 
    if (x == SPAM)
    {
        sprintf(final, "%s%s", pathRepSpam, f2);
    }
    if (x == NOTSPAM)
    {
        sprintf(final, "%s%s", pathRepNotSpam, f2);
    }
 
    res = LZW(final, "tmp2");
 
    if (res < 0)
    {
        perror("kolmo : La compression a échouée ! \n");
        return ECHEC_COMPRESSION;
    }
 
    concatFiles(f1, f2, x, pathRepMail, pathRepSpam, pathRepNotSpam);
 
    res = LZW("temp3", "tmp3");
 
    if (res < 0)
    {
        perror("kolmo : La compression a échouée ! CONCATFILES !\n");
        return ECHEC_COMPRESSION;
    }
 
    /* On va calculer la taille des 3 fichiers compressés */
 
    file1 = fopen("tmp1","rb");
    file2 = fopen("tmp2","rb");
    concat = fopen("tmp3","rb");
 
    if ((file1 == NULL) || (file2 == NULL) || (concat == NULL))
    {
        perror("kolmo : Erreur ouverture fichier");
        return ECHEC_OUVERTURE_FICHIER;
    }
 
    tailleA = fsize(file1);
    tailleB = fsize(file2);
    tailleAB = fsize(concat);
 
    fclose(file1);
    fclose(file2);
    fclose(concat);
 
    /* Application de l'algo de Kolmo */
 
    return distanceKolmo(tailleA, tailleB, tailleAB);
 
}

et enfin la fonction distanceKolmo :

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
 
double distanceKolmo(double tailleA, double tailleB, double tailleAB)
{
    double resultat = 0.;
    double min = minKolmo(tailleA, tailleB);
 
 
    if (tailleA > tailleB)
    {
        resultat =  1.0 - (tailleA + tailleB - tailleAB)/min;
 
        return resultat;
    }
 
    if (tailleB > tailleA)
    {
        resultat =  1.0 - (tailleA + tailleB - tailleAB)/min;
 
        return resultat;
    }
 
 
    return SUCCES;
 
}

Voila ça, ça correspond au remplissage des tableaux, aprés je les trie dans une autre fonction (en ce moment je trie avec le tri par maximum).

merci.

Tri a bulles

C

Vue hybride

Discussions similaires

Partager

Partager