[liste] Problème de tri rapide

**sorry60** · 30/04/2006, 19h10

Bonjour,

Toujours dans mon enorme tp sur les listes (derniere question

), j'ai un probleme pour le tri rapide (quicksort).
On a un pseudo algo :

Pour le tri rapide :
Le tri rapide avec les listes utilise les fonctions void extraire_element
(qui extrait un element) et void concat qui concatène deux listes
(fonctions définies en Q5 et Q7).
si la liste n'est pas réduite à un el ou vide :
- prendre comme pivot le premier elmnt de la liste (c'est plus
adapté pour la liste où on a directement accès au premier élément).
- créér deux listes liste_inf et liste_sup contenant respectivement
les élémnts inférieurs et supéreurs au pivot. Pour ce faire on parcourt la
liste et on extrait chaque elmnt en le ventilant ds la bonne liste.
- trier les deux sous-listes récursivement
- concaténer liste_inf, pivot , et liste_sup ( en modifiant
éntuellemnt la tete de liste).

Voila le code que j'ai pu en tiré :

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
/* Fonction qui trie une liste avec l'algo de tri rapide */
void tri_rapide (P_un_element *liste)
{
    P_un_element pivot, tete, liste_inf, liste_sup;
    if ( *liste && ((*liste)->suiv) )
    {
        pivot = *liste;
        tete = *liste;
        while ( *liste )
        {
            if ( pivot->elem_val < (*liste)->elem_val )
                inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));
            else
                inserer_element_fin(&liste_inf,rechercher_element(*liste,(*liste)->elem_val));
            *liste = (*liste)->suiv;
        }
        *liste = tete;
        tri_rapide(&liste_sup);
        tri_rapide(&liste_inf);
        concat (liste,liste_inf);
        *liste = tete;
        concat(liste,pivot);
        *liste = tete;
        concat(liste,liste_sup);
        *liste = tete;
    }
}

Qui utilise donc les fonctions concat, inserer_element et rechercher_element ecrites plus tot :

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
/* fonction qui ajoute L2 dans le liste L1 */
void concat (P_un_element *l1, P_un_element l2)
{
    /* si l2 est vide, rien a faire */
    if ( !l2 )
        return;
    else
    {
        /* on ajoute l2 */
        while ( l2 )
        {
            inserer_element_fin(l1,creer_element(l2->elem_val));
            l2 = l2->suiv;
        }
    }
}
 
/* fonction retourne un certain element s'il est dans la liste */
P_un_element rechercher_element (P_un_element liste, Tval val )
{
    /*while ( liste && ( cmpval(liste->elem_val,val) != 0 ) ) */
    while ( liste && ( liste->elem_val != val ) )
    {
        liste = liste->suiv;
    }
    if ( !liste )
    {
        printf("L'element n'est pas dans la liste !\n");
        return NULL;
    }
    else
        return liste;
}
 
/* fonction qui insere un element a la fin de la liste */
void inserer_element_fin (P_un_element *liste, P_un_element el)
{
    if ( !(*liste) )
    {
        /* la liste est vide, il suffit de creer un element */
        *liste = creer_element(el->elem_val);
    }
    else
    {
        /* on garde en memoire la tete */
        P_un_element tete = *liste;
        /* on se deplace jusqu'au dernier element */
        while ( (*liste)->suiv )
            *liste = (*liste)->suiv;
        /* on insere l'element a la fin */
        (*liste)->suiv = el;
        *liste = (*liste)->suiv;
        (*liste)->suiv = NULL;
        /* on remet liste sur la tete */
        *liste = tete;
    }
}

Voila je tombe sur un segmentation fault

Mes yeux tombent par terre, j'espere que vous y verez plus clair.
Merci pour votre aide

Sorry

**fearyourself** · 01/05/2006, 02h56

Code :

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

1
2
3
4
            if ( pivot->elem_val < (*liste)->elem_val )
                inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));
            else
                inserer_element_fin(&liste_inf,rechercher_element(*liste,(*liste)->elem_val));

liste_sup et liste_inf ne sont pas initialisés. Par contre, ton utilisation des pointeurs et le fait que tu caches les pointeurs avec un typedef va te jouer des tours... Il faudra faire attention...

Jc

**sorry60** · 01/05/2006, 11h36

Envoyé par fearyourself

Par contre, ton utilisation des pointeurs et le fait que tu caches les pointeurs avec un typedef va te jouer des tours... Il faudra faire attention...

Jc

Oui je sais, je trouve pas ça tres futé mais c'est imposé par l'exercice

Merci pour ta reponse, je vais corriger ça

**sorry60** · 01/05/2006, 12h26

aie ! j'ai initialisé liste_inf et liste_sup mais j'ai toujours l'erreur de segmentation

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
/* Fonction qui trie une liste avec l'algo de tri rapide */
 void tri_rapide (P_un_element *liste)
 {
     P_un_element pivot, tete, liste_inf, liste_sup;
 
     liste_inf = malloc(sizeof(Un_element));
     liste_sup = malloc(sizeof(Un_element));
     if ( *liste && ((*liste)->suiv) && liste_inf && liste_sup )
     {
         pivot = *liste;
         tete = *liste;
         while ( *liste )
         {
             if ( pivot->elem_val < (*liste)->elem_val )
                inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));
             else
                inserer_element_fin(&liste_inf,rechercher_element(*liste,(*liste)->elem_val));
             *liste = (*liste)->suiv;
         }
         *liste = tete;
         tri_rapide(&liste_sup);
         tri_rapide(&liste_inf);
         concat (liste,liste_inf);
         *liste = tete;
         concat(liste,pivot);
         *liste = tete;
         concat(liste,liste_sup);
         *liste = tete;
     }
 }

Je vois pas d'où ça vient car je respecte l'algo donné avec l'exo

**crocodilex** · 01/05/2006, 13h17

Envoyé par sorry60

Code :

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

1
2
3
4
      P_un_element pivot, tete, liste_inf, liste_sup;
 
     liste_inf = malloc(sizeof(Un_element));
     liste_sup = malloc(sizeof(Un_element));

"P_un_element pivot" est-il vraiment de type pointeur ?
Et "Un_element" est de quel type ?

Montres nous les définitions de ces 2 types...

**diogene** · 01/05/2006, 13h37

Code :

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

1
2
     liste_inf = malloc(sizeof(Un_element));
     liste_sup = malloc(sizeof(Un_element));

Cette initialisation est incorrecte puisqu'alors, liste_inf et liste_ sup ne sont plus vides mais possèdent un élément non initialisé.
Dans la fonction inserer_element_fin :

Code :

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

1
2
3
4
5
6
7
8
 
    if ( !(*liste) )
    ..... 
   else
    {
        P_un_element tete = *liste;
        while ( (*liste)->suiv )
    ....

le test de liste vide échoue donc et on arrive à (*liste)->suiv qui plante puisque le membre suiv n'a pas été initialisé.

Il faut initialiser liste_inf et liste_sup à NULL

**sorry60** · 01/05/2006, 15h02

Envoyé par diogene

Il faut initialiser liste_inf et liste_sup à NULL

Exact, desolé aujourd'hui je suis vraiment trop nul.. faut dire que ça fait 1 semaine que je mange de ce tp sur les listes, ça commence à me sortir par les yeux !

Merci pour vos reponses, je vais corriger mon code

**sorry60** · 01/05/2006, 15h12

Voila c'est bon, plus d'erreur de segmentation

Par contre le tri n'a aucun effet, la liste est rendu sans aucun changement

Test de la fonction tri_rapide
Notre liste en vrac :
Valeur element : 8, pointeur suivant : 0x943e158
Valeur element : 11, pointeur suivant : 0x943e0a8
Valeur element : 4, pointeur suivant : 0x943e238
Valeur element : 7, pointeur suivant : 0x943e208
Valeur element : 2, pointeur suivant : 0x943e228
Valeur element : 6, pointeur suivant : 0x943e1e8
Valeur element : 18, pointeur suivant : 0x943e038
Valeur element : 1, pointeur suivant : (nil)
Notre liste triee avec tri_rapide :
Valeur element : 8, pointeur suivant : 0x943e158
Valeur element : 11, pointeur suivant : 0x943e0a8
Valeur element : 4, pointeur suivant : 0x943e238
Valeur element : 7, pointeur suivant : 0x943e208
Valeur element : 2, pointeur suivant : 0x943e228
Valeur element : 6, pointeur suivant : 0x943e1e8
Valeur element : 18, pointeur suivant : 0x943e038
Valeur element : 1, pointeur suivant : (nil)

Voila la definition du type employé :

Code :

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

1
2
3
4
5
typedef struct _un_element
{
    Tval elem_val;
    struct _un_element *suiv;
} Un_element, * P_un_element;

**diogene** · 01/05/2006, 18h31

Par contre le tri n'a aucun effet, la liste est rendu sans aucun changement

Pas étonnant :

Code :

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

1
2
3
4
 
     liste_inf = NULL;
     liste_sup = NULL;
     if ( *liste && ((*liste)->suiv) && liste_inf && liste_sup ){....

Pourquoi toutes ces conditions ?
Maintenant, je crois que d'autres questions plus ennuyeuses vont se révéler ensuite.

Code :

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

1
2
3
4
5
6
7
8
9
10
         pivot = *liste;
         tete = *liste;
         while ( *liste )
         {
             if ( pivot->elem_val < (*liste)->elem_val )
                inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));
             else
                inserer_element_fin(&liste_inf,rechercher_element(*liste,(*liste)->elem_val));
             *liste = (*liste)->suiv;
         }

normalement, cette partie de code détache les éléments de *liste pour les ranger dans liste_sup et liste_inf et à la fin, *liste devrait être vide; Je ne pense pas que inserer_element_fin réalise le décrochage correct de *liste

Code :

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

1
2
  if ( pivot->elem_val < (*liste)->elem_val )
       inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));

A coup sur, rechercher_element va répondre *liste

Code :

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

1
2
  if ( pivot->elem_val < (*liste)->elem_val )
       inserer_element_fin(&liste_sup,*liste);

Code :

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

1
2
3
4
5
6
7
8
9
         *liste = tete;
         tri_rapide(&liste_sup);
         tri_rapide(&liste_inf);
         concat (liste,liste_inf);
         *liste = tete;
         concat(liste,pivot);
         *liste = tete;
         concat(liste,liste_sup);
         *liste = tete

Cette partie reconstruit *liste à partir de liste_sup , pivot et liste_inf. A quoi servent ces *liste = tete qui place systématiquement la tête de liste sur le pivot ?

Code :

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

1
2
3
4
5
6
void inserer_element_fin (P_un_element *liste, P_un_element el)
{
    if ( !(*liste) )
    {
        *liste = creer_element(el->elem_val);
    }

Pourquoi créer un nouvel élément ? L'algorithme ne doit pas créer de nouveaux éléments (qu'il faudrait détruire ensuite) mais manipuler le chaînage des éléments existants.

**sorry60** · 01/05/2006, 20h06

Ok ok merci pour ton aide, je reprendrai ça au calme demain car aujourd'hui jsuis overdosé des listes...

Merci beaucoup pour ton aide

Sorry

**sorry60** · 01/05/2006, 20h11

Je reponds quand meme à tes questions :

Envoyé par diogene

Pas étonnant :

Code :

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

1
2
3
4
 
     liste_inf = NULL;
     liste_sup = NULL;
     if ( *liste && ((*liste)->suiv) && liste_inf && liste_sup ){....

Pourquoi toutes ces conditions ?

Je suppose que tu parles de liste_inf && liste_sup, en effet j'ai oublié de les enlever apres avoir enlevé le malloc, c'est sur que ça risquait pas de trier quelque chose

Envoyé par diogene

Maintenant, je crois que d'autres questions plus ennuyeuses vont se révéler ensuite.

Code :

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

1
2
3
4
5
6
7
8
9
10
         pivot = *liste;
         tete = *liste;
         while ( *liste )
         {
             if ( pivot->elem_val < (*liste)->elem_val )
                inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));
             else
                inserer_element_fin(&liste_inf,rechercher_element(*liste,(*liste)->elem_val));
             *liste = (*liste)->suiv;
         }

normalement, cette partie de code détache les éléments de *liste pour les ranger dans liste_sup et liste_inf et à la fin, *liste devrait être vide; Je ne pense pas que inserer_element_fin réalise le décrochage correct de *liste

Oui j'avais vu ce probleme et remplacé la fonction de recherche par une fonction qui extrait un element.
Mais j'ai oublié de reposter la bonne version, le reste ne change pas.

Envoyé par diogene

Code :

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

1
2
  if ( pivot->elem_val < (*liste)->elem_val )
       inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));

A coup sur, rechercher_element va répondre *liste

Code :

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

1
2
  if ( pivot->elem_val < (*liste)->elem_val )
       inserer_element_fin(&liste_sup,*liste);

Code :

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

1
2
3
4
5
6
7
8
9
         *liste = tete;
         tri_rapide(&liste_sup);
         tri_rapide(&liste_inf);
         concat (liste,liste_inf);
         *liste = tete;
         concat(liste,pivot);
         *liste = tete;
         concat(liste,liste_sup);
         *liste = tete

Cette partie reconstruit *liste à partir de liste_sup , pivot et liste_inf. A quoi servent ces *liste = tete qui place systématiquement la tête de liste sur le pivot ?

Idiot en effet.

Envoyé par diogene

Code :

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

1
2
3
4
5
6
void inserer_element_fin (P_un_element *liste, P_un_element el)
{
    if ( !(*liste) )
    {
        *liste = creer_element(el->elem_val);
    }

Pourquoi créer un nouvel élément ? L'algorithme ne doit pas créer de nouveaux éléments (qu'il faudrait détruire ensuite) mais manipuler le chaînage des éléments existants.

Ici je crée un element car la liste est vide.

**diogene** · 01/05/2006, 20h15

Ici je créé un element car la liste est vide.

Non, insère simplement l'élément en argument.

Ceci devrait marcher.

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
 
/*---------------------------------------------*/
void inserer_element_fin (P_un_element *liste, P_un_element el)
{
   if ( !(*liste) ) *liste = el;
    else
    {
        P_un_element tete = *liste;
        while ( tete->suiv )tete = tete->suiv;
        tete->suiv = el;
    }
}
/*---------------------------------------------*/
 void tri_rapide (P_un_element *liste)
 {
     P_un_element pivot , courant;
     P_un_element liste_inf = NULL;
     P_un_element liste_sup = NULL;
     if (*liste)
     {
         pivot = *liste ;
         *liste = (*liste)->suiv;
         pivot->suiv = NULL;
         while ( *liste )
         {
             courant = (*liste) ;
             *liste = (*liste)->suiv;
             courant->suiv = NULL;
             if ( pivot->elem_val < courant->elem_val )
                inserer_element_fin(&liste_sup,courant);
             else
                inserer_element_fin(&liste_inf,courant);
         }
        tri_rapide(&liste_sup);
        tri_rapide(&liste_inf);
        inserer_element_fin(liste,liste_sup);
        inserer_element_fin(liste,pivot);
        inserer_element_fin(liste,liste_inf);
     }
 }