Discussion :

[takout]

Bonjour à tous,

Je souhaiterai écrire un programme qui range et trie les éléments d'une matrice qui se situe dans un fichier text. Mon souci c'est que lors du tri mon programme n'affiche pas le bon résultat. J'ai remarqué qu'avec des nombres décimaux proches de zéros (0.5 par exemple) mon programme affiche n’importe quoi, tandis qu'avec d'autres nombres il semble fonctionner.

Quelqu'un peut t'il m'aider s'il vous plaît ?

voici mon main :

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
 
 
 
 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include "quicksort.h"
 
 
 
 
int main(){
 
 double **A;
 
 int i,j,k=0,nrow,ncol,size_v=4*4;
 double tridoublon[4*4];
 FILE* fichier = NULL;
 nrow=4;ncol=4;
 
  /* lecture du fichier */
  fichier=fopen("test.txt","r");
 
   A=malloc(nrow*sizeof(double*));
 
    for(i=0;i<nrow;i++)
   { A[i]=malloc(ncol*sizeof(double)); }
 
 
     if (fichier != NULL)
    {
	for(i=0;i<nrow;++i){
             for(j=0;j<ncol;++j){ fscanf(fichier, "%lf", &A[i][j]); }}
    }
 
  fclose(fichier);
 
   /*creation du vecteur */
     for (i=0;i<nrow;++i){
     for(j=0;j<ncol;++j){tridoublon[k]=A[i][j]; ++k;}}
 
   /*trie du vecteur */
    quicksort(tridoublon,0,size_v-1);
     for(i=0;i<size_v;++i)
     { printf("%lf \n",tridoublon[i]);}
 
  for(i=0;i<nrow;i++){
  for(j=0;j<ncol;j++){
 
  printf("%lf \t",A[i][j]);
  } printf("\n");
  } 
 
 return(0); 
 }

mes fonctions :

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
 
 
#include<stdio.h>
#include<stdlib.h>
#include"quicksort.h"
 
#define Malloc(n,type) (type*)malloc((n)*sizeof(type))
#define Free(p) free(p); p=NULL
 
void echanger(double tableau[], int a, int b)
{
    int temp = tableau[a]; 
    tableau[a] = tableau[b];
    tableau[b] = temp;
}
 
 
void quicksort(double *v, int gauche,  int droit)
{
   int i, dernier;
 
 
if(gauche>=droit)
return;
 
echanger(v,gauche,(gauche+droit)/2); /* i */
/*place l'élément du centre en v[0] */
dernier=gauche;
for(i=gauche+1;i<=droit;++i)
 
if (v[i]<v[gauche])
 
echanger(v,++dernier,i);
 
echanger(v,gauche,dernier);
/* remet en place l'élément de partage */
quicksort(v,gauche,dernier-1);
quicksort(v,dernier+1,droit);
}
 
 
 
int nombre_doublon(double *tab, int size)
{ 
  register int i;
   int k=1;
   for(i=0;i<size-1;++i)
   {  
     if(tab[i]!=tab[i+1])
     { ++k;}
   }
   return(k);
}
 
int suprime_doublon(double **res,double *tab,int size)
{  
   double *t;
   int i,j,n_nondoublon;
   j=0;
 
    n_nondoublon=nombre_doublon(tab,size);
    t=Malloc(n_nondoublon,double);
 
   t[j]=tab[0];
   for(i=0;i<size;++i)
   {
      if(t[j]!=tab[i])
      { ++j;
      	t[j]=tab[i]; 
      }
 
   }  
   *res=t; 
   return(n_nondoublon);    
 }

et ma matrice dans un fichier text :

Code :

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

1
2
3
4
5
 
0.7	0.6	0.5	0.4
0.8	0.5	0.4	0.3
0.9	0.4	0.3	0.2
0.0	0.3	0.2	0.1

mon objectif serait de supprimer les doublons du vecteur après le tri.

Cordialement, Takout

[droggo]

Kie,

Relis ton code (ce que tu as écrit, pas ce que tu penses avoir fait !), et tu trouveras.

[Neckara]

Kie,

Relis ton code (ce que tu as écrit, pas ce que tu penses avoir fait !), et tu trouveras.

En quoi est-ce que cette réponse aide le PO?
S'il vient poster ici et s'il montre son code c'est justement qu'il sait qu'il sait sûrement qu'il y a une erreur dedans et qu'il a sûrement déjà relu plusieurs fois son algorithme sans trouver ce qui lui échappe....
En gros il dit qu'il y a une erreur dans son code et qu'il n'arrive pas à la trouver, et toi tu lui répond de relire son code car il y a une erreur dedans...


Je pense que ton erreur vient de là :

Code :

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

1
2
3
4
 
echanger(v,gauche,(gauche+droit)/2); /* i */
/*place l'élément du centre en v[0] */
dernier=gauche;

dernier ne serait-il pas plutôt égal à (gauche+droit)/2 ?

[takout]

Non je ne pense pas.
J'ai essayé avec votre proposition mais ça ne marche pas.
ce qui est bizarre c'est que pour cette matrice ça marche :

Code :

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

1
2
3
4
5
6
 
 
7.0	6.0	5.0	4.0
8.0	5.0	4.0	3.0
9.0	4.0	3.0	2.0
0.0	3.0	2.0	1.0

J'ai d'abord pensé à un problème de type d'une variable mais je ne vois pas où cela à lieu. Je ne vois pas où est l'erreur.

[Neckara]

Je pense déjà que ton algorithme est complètement faux.

- Choix du pivot arbitraire, on va dire le premier élément.

- Déplacement du pivot à la toute fin (ou au tout début) :

Code :

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

echanger(v, 0, fin)

- Parcours du tableau dans les deux sens, on s'arrête quand on se 'rencontre'. Dans le sens de lecture qui commence à droite, on va échanger les valeur supérieur au pivot avec les valeurs inférieur au pivot rencontré lors de la lecture dans l'autre sens.

Code :

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

1
2
3
4
5
6
7
8
 
int sens1 = 0, sens2 = fin - 1;
while(sens1 != sens2)
{
        while(sens1 != sens2 && v[sens1] < pivot) sens1++;
        while(...) ...; //très similaire pour l'autre sens.
       echanger(v, sens1, sens2);
}

- On échange le pivot avec le dernier éléments qu'on a parcouru (ou celui juste d'après) puis on refait le quick sort à gauche et à droite du pivot.

Code :

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

1
2
3
4
5
 
if(pivot > v[sens2]) sens2 +=1;
echanger(v, sens2, fin);
triRapide(v, 0, sens2-1);
triRapide(v, sens2+1, fin);

Bon, je l'ai fait vite fait mais le principe est là.

[droggo]

Hie,

En quoi est-ce que cette réponse aide le PO?

Ça sert à lui expliquer de relire correctement son code, et pas en diagonale comme on est tenté de le faire trop souvent quand on est l'auteur.

Pour info, il faut regarder vers les transtypages dans la fonction echanger.

Il est possible qu'il y ait d'autres erreurs, je n'ai pas cherché plus loin, mais vu que ça marche quand les valeurs mises dans le tableau de double sont entières ...

[Neckara]

Je n'avais pas vu cette erreur et ce n'est pas faute d'avoir relu plusieurs fois en détail le code. C'est le genre d'erreur bête qu'on peut voir de nombreuses fois sans ''titler''.

Sinon, j'ai essayer de regarder ce que donne exactement son algorithme, je confirmes que l'algorithme est faux.

[takout]

re,

L'erreur est bien là, " le int temp=tableau[a]".
Je cherchais une erreur de ce type mais je n'arrivais avoir là où elle se situais.
Sûrement que je devais lire en diagonale.

Neckara, j'ai essayé un algorithme du même type que celui que tu as expliqué. Je l'ai trouvé sur un des sites concurrents à développez. Mais je l'ai testé sur des matrices de grandes tailles et j'ai eu parfois des segmentations faults. Je me suis donc orienté vers un autre algo.

voici l'algo que j'ai testé :

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
 
 
void quicksort1(double  *tableau, int debut, int fin)
{
    int gauche = debut-1;
    int droite = fin+1;
    const int pivot = tableau[debut];
 
 
 
    if(debut >= fin)
     {return;}
  while(1)
    {
        do{
        droite--;
        }while(tableau[droite] > pivot);
 
        do{
        gauche++; 
        }while(tableau[gauche] < pivot);
 
        if(gauche < droite)
         {echanger(tableau, gauche, droite);}
        else 
        {break;}
    }
 
    quicksort(tableau, debut, droite);
    quicksort(tableau, droite+1, fin);
}

Si tu vois où est le problème algorithme de cette implémentation dis le moi car j'ai cherché j'ai pas trouvé. Je me suis dis que c'est peut être dû aux doublons
Je vous remercie pour votre aide.

[takout]

Neckara donne moi un contre exemple sur lequel l’algorithme que j'utilise ne fonctionne pas stp. J'ai testé sur mes exemples et ça donne de bons résultats.

[droggo]

Loa,

Mais je l'ai testé sur des matrices de grandes tailles et j'ai eu parfois des segmentations faults.

Alors il doit effectivement y avoir des erreurs, sinon il n'y a pas de raisons.

Au passage, évite de parler de matrices alors que tu utilises de simples tableaux monodimensionnels (matrice = 2 dimensions).