[liste] Problème de tri rapide
Bonjour,
Toujours dans mon enorme tp sur les listes (derniere question :D), j'ai un probleme pour le tri rapide (quicksort).
On a un pseudo algo :
Citation:
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:
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:
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 :aie:
Mes yeux tombent par terre, j'espere que vous y verez plus clair.
Merci pour votre aide
Sorry
