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

[Neckara]

L'algorithme que tu as testé est lui aussi faux...
C'est pourtant pas difficile de suivre un tel algorithme non?

Sinon 3 erreurs sur ton algorithme :

1) echanger(v,gauche,(gauche+droit)/2); est inutile, tu fais un déplacement pour rien.
Quand je dit :

- Choix du pivot arbitraire, on va dire le premier élément.
- Déplacement du pivot à la toute fin (ou au tout début) :

Il est plus malin de choisir directement en pivot le dernier (ou le premier élément) on gagne un déplacement par appel de la fonction de trie.

2) Tu parcours de la moitié de ton tableau à la fin et dès que tu rencontre un élément plus petit que le pivot, tu l'échange avec l'élément d'indice dernier puis tu incrémentes dernier.
Or si l'élément d'indice dernier est lui aussi plus petit que pivot, tu as un problème.

3) Si il y a moins d'élément 'à droite' qui sont plus grand que le pivot que d'éléments 'à gauche'. Si les derniers élément 'à gauche' sont plus grand que le pivot, ils restent à gauche.


EDIT : pour l'algorithme que tu as testé, c'est tout simplement n'importe quoi. Essaye de voir ce qu'il fait réellement.

[takout]

Euh je m'en excuse , je suis un matheux c'est pour ça que pour moi les tableaux quelques soient leurs dimensions sont des matrices.

Pour être sincère je ne suis pas l'investigateur de cet algorithme mais je pense qu'il fonctionne.

Code :

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

1
2
 
echanger(v,gauche,(gauche+droit)/2);

Cette instruction indique que le pivot est la médiane du tableaux que je passe dans la première case du tableaux. C'est vrai que pour l'optimisation du code ta remarque est juste.

Code :

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

1
2
3
4
5
 
for(i=gauche+1;i<=droit;++i)
{ 
   if (v[i]<v[gauche]){echanger(v,++dernier,i);}
}

Là, je parcoure tout le tableau sauf le pivot.
Si un élément est inférieur au pivot je le permute avec l'élément qui est à l'indice correspondant à dernier (dernier est incrémenté pour ne pas échanger un élément inférieur au pivot). Ceci implique que dernier est toujours inférieur au pivot.
J'ai maintenant trois parties dans mon tableaux, une avec le pivot, la partie de gauche (où tous les éléments sont inférieur à pivot) et de droite (les éléments supérieur au pivot)

Code :

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

1
2
 
echanger(v,gauche,dernier);

Je mets le pivot à la bonne place. Dernier est l'élément du tableaux le plus à droite qui est inférieur au pivot, en faisant l'échange " pivot dernier "je place pivot à la bonne place.
Puis je fais la récursion sur les deux sous tableaux privés du pivot.

Ta troisième remarque je n'ai pas tous compris. Donne moi l'exemple d'un tableau ou ça ne marcherai pas.

[Neckara]

Autant pour moi, j'ai mal lu ton algorithme, j'ai cru que tu parcourais du milieu du tableau à la fin alors que tu parcours du début à la fin (sans inclure le pivot), il faut dire que ton algorithme n'est pas très clair et qu'il est un peu tiré par les cheveux. Il m'a fallu un moment pour comprendre son fonctionnement^^

Ton algorithme marche mais ce n'est toujours pas du quick sort.

Si tu as :
pivot : 2
Liste : 3 1 1 1 1 1 1 1 1 1 1 1 1 1

Tu vas avoir 13 déplacements...

Avec le quick sort, tu n'en auras 1 seul (cf l'algo que je t'ai donné)

Et pire ! Si tu as :
1 1 1 1 1 1 1 1 1

Tu vas faire 9 déplacements qui n'ont pas lieu d'être.

EDIT : on peut aussi optimiser mon algorithme avec :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
while(1)
{
            while(tab[sens1] < pivot) 
            {
                   sens1++;
                   if(sens1 >= sens2)
                          goto fin;//sorte de break 2 : casse deux boucles whiles et va à la fin de la dernière
             }
              //a peu près la même chose pour l'autre sens
             echanger(tab, sens1, sens2);
}
fin :

ceci évite plusieurs comparaisons par tour de boucle.
Je ne sais pas s'il existe une méthode plus rapide.

Par contre attention, ne jamais utiliser de goto !
En fait, c'est plus compliqué que cela et sujet à de grands débats.
On va dire que la très grande majorité des utilisations de goto sont des erreurs donc on préfère dire aux débutants et aux un peu plus confirmés de ne pas les utiliser.
Mais le goto peut être très utile pour optimiser un code critique mais il existe toujours un moyen de faire sans.

Le goto n'est pas si mauvais que cela, mais c'est l'utilisation que certaines personnes en fait qui est très mauvaise.
Le goto permet en effet trop de lirbertés.

Mais il faut bien comprendre que les break; et les continue; sont des goto déguisés et limités (là je fait une sorte de break 2; donc ça passe encore un peu^^).

Donc en bref ne réutilise pas le goto ailleurs. ll y a même de forte chances que tu n'ai jamais à l'utiliser dans ta carrière donc bon^^

Merci de ne pas rentrer dans le débat pour/contre GOTO, il existe plein d'autres sujets en parlant^^

[droggo]

Koa,

Oui, mais discuter de la rapidité de différents algos de tri ne sert pas à grand chose si on n'a que des tableaux de petite taille à trier.

ps : Ok, takout semble vouloir trier de grands tableaux ... mea culpa

[takout]

C'est clair que le quicksort n'est pas très efficace sur des tableaux déjà triés.
l'algo que j'ai utilisé n'est qu'une variante de l'algo de base du quicksort.

[Neckara]

Pourquoi utiliser une variante (de mon point de vu) plus compliqué (et donc moins compréhensible) et plus lente que le quick sort ?

Au pire pour chacun des deux algos :

Code :

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

1
2
3
4
5
6
 
Tour/Nb déplacements                  Quick sort             Ton algo
0                                     (n+1)/2                 n
1                                     (n)/2                   n-1
2                                     (n-1)/2                  n-2
.....

En moyenne, je ne peux pas vraiment dire le nombre de déplacements, mais ton algorithme fait, je pense, en moyenne 2 fois plus de déplacements que le quick sort. Sachant que les déplacements constituent le gros de l'algorithme on peut presque dire que ton algo est un peu moins de 2 fois plus lent que le quick sort.