Discussion :

[verazano]

Bonjour ,

j'ai un problème sur le tri rapide ou quicksort.
Ma fonction partition marche trés bien voici son prototype:

void part(int tab[],int deb,int fin,int pivot);

le problème est dans ma fonction qui va faire le trie :

Code :

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

1
2
3
4
5
6
7
8
void quicksort(int tab[],int deb,int fin)
      {
                 int pivot;
                 pivot=tab[1];
                 part(tab,deb,fin,pivot);
                 quicksort(tab,deb,pivot-1);
                 quicksort(tab,pivot+1,fin);
      }

cette fonction me donne un segmentation fault depuis 2 heures je tourne en rond , je n'arrive pas à voir d'où vient l'erreur.
je viens vous demander à l'aide en vous remerciant d'avance.

[stephl]

Il faudrait peut-être une condition de fin de récursion.

[verazano]

mince j'ai oublie de mettre mon critère d'arrêt et en plus je sais lequel c'est

[verazano]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
void quicksort(int tab[],int deb,int fin)
{
        int pivot;
        pivot=tab[1];
        if(deb<=fin)
        {
                part(tab,deb,fin,pivot);
                quicksort(tab,deb,pivot-1);
                quicksort(tab,pivot+1,fin);
        }
}

voilà mon critère d'arrêt

[Emmanuel Delahaye]

Code :

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

1
2
3
4
5
 
void quicksort(int tab[],int deb,int fin)
{
<...>
                part(tab,deb,fin,pivot);

voilà mon critère d'arrêt

et part() ? On est pas devins...

[droggo]

Hoï,

et part() ? On est pas devins...

Si, d'ailleurs j'avais prévu que quelqu'un réagirait !!

[verazano]

bah eux c'est ma fonction partition si vous la voulez :

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
 
int  part(int tab[],int deb,int fin)
{
        int pivot;
        int g=deb;
        int d=fin;
        int p;
        pivot=tab[0];
        p=tab[pivot];
        g=g+1;
        while (g<d)
        {
                while((g<=fin)&&(tab[g]<p))
                        g=g+1;
                while((d>=deb)&&(tab[d]>p))
                        d=d-1;
                if((tab[g]>tab[d])&&(g<d))
                        swap(tab,g,d);
        }
        return d;
}

par contre la fonction swap je crois que j'ai pas besoin de vous la donner

Petite précision entre temps j'ai décidé de plus m'embêter du pivot et de le prendre à tab[0]
Donc l'entrée pivot de ma fonction part et à enlever

Si vous trouvez que j'ai un peu trop "éclaté" mes fonctions c'est normal , c'était pour essayer au maximum de clarifier mon code pour voir mon erreur

Bon comme on dit la nuit porte conseil , je vais donc arrêter pour ce soir et demain reprendre plus tranquillement.

[souviron34]

et si :

1) pivot-1 est négatif
2) pivot+ est plus grand que la dimension de ton tableau
3) là tu raisonnes sur la VALEUR de tab. Si tab[0] ou tab[1] est < 0 ou > dimension de ton tableau ??

[verazano]

la dimension du tableau ?
Je comprends pas très bien


bah oui on compare la valeur du pivot et la valeur du tableau mais je vois pas trop où est le problème .

[verazano]

ayez j'ai résolu le segmentation fault

Cela marche maintenant enfin que pour des tableaux comprenant un nombre paire de valeur . Sinon sur les tableaux comprenant un nombre impair de valeur j'ai une valeur qui n'est pas trié .