Se connecter avec
S'enregistrer | Connectez-vous

[Code C] Problème de quicksort

Dernière réponse : dans Programmation

Bonjour à tous !! :hello: 

Voilà, comme indiqué dans le titre, j'ai un problème dans ma fonction quicksort (tri rapide). Cette fonction est intégrée à un programme qui recréer un algortihme génétique (en version simplifiée). Suelement voilà, le quicksort ne s'effectue pas correctement et provoque une erreur de segmentation. C'est un algorithme récursif, dans la théorie eil fonctionne (par rapport aux algos sur le net) mais ça ne va pas plus loin ...

Si quelqu'un aurait la gentillesse de m'aider ça serait sympa ;) 

Donc voici la fonction en question :

Edit :

Si vous avez des questions concernant le code que vous n'avez pas compris, n'hésitez pas à le demander ;) 

Merci pour votre aide :jap: 

Autres pages sur : code probleme quicksort

Lassé par la pub ? Créez un compte

Citation :
il est un peu tard pour réfléchir mais tu as surement des problèmes de mémoire vu que tu ne libère pas la mémoire créée pour le pivot et les autres pointeurs ?

d'ailleur, sont-ils vraiment utiles ?


Euh oui je ne libère pas la mémoire effectivement. Ca peut être à l'originie du problème ?

A mon avis oui ils sont utiles vu que j'en ai besoin pour manipuler les donnés :) 

Citation :
je dirait meme qu'aucun malloc n'est nécessaire ...

ps : je connais pas l'algo de quicksort par coeur


Pourquoi ce n'est pas nécessaire ? Il en faut pour allouer de la mémoire aux nouvelles variables non ?

PS : merci de répondre aussi tard :D 
Je suis pas un as de la prog :jap: 

Citation :
bon, apres avoir réfléchi, il te faut effectiver créer les deux populations temporaires (p1 et p2) mais faut les nettoyer apres la concatenation


Ben la fonction concat est dans le return du quicksort et vu que c'est du récursif, si je les libère ça va foutre le dawa non ?

Citation :
is_empty_pop : tu devrais vérifier que le pointeur qu'on te passe ne soit pas null
  1. is_empty_pop(NULL); //< pouf ! segfault


  1. BOOL is_empty_pop (Population pop)
    

  2. {
    

  3. 	if ((pop->NextIndiv == NULL) && (pop->people == NULL)) // Teste si la population est vide
    

  4. 	  {
    

  5. 		return TRUE;
    

  6. 	  }
    

  7. 	else 
    

  8. 	  {
    

  9. 		return FALSE;
    

  10. 	  }
    

  11. }


La condition du if tel qu'elle est actuellement ne vérifie pas si c'est vide ?

patcoll a dit :
  1. BOOL is_empty_pop (Population pop)
    

  2. {
    

  3. 	if ((pop->NextIndiv == NULL) && (pop->people == NULL)) // Teste si la population est vide
    

  4. 	  {
    

  5. 		return TRUE;
    

  6. 	  }
    

  7. 	else 
    

  8. 	  {
    

  9. 		return FALSE;
    

  10. 	  }
    

  11. }


La condition du if tel qu'elle est actuellement ne vérifie pas si c'est vide ?

non, elle verifie qu'on a spécifier une valeur et qu'il n'y pas de suivant...

patcoll a dit :
Ben la fonction concat est dans le return du quicksort et vu que c'est du récursif, si je les libère ça va foutre le dawa non ?

bha faut
1/ recuperer la valeur de concat dans une variable "r"
2/ nettoyer la memoire
3/ return r

patcoll a dit :
  1. Population retour;
    

  2. 			retour = concat( (insert_pop_tail(quicksort(p1),(pivot->people))), (quicksort(p2)) );
    

  3. 			free (retour);
    

  4. 			return retour;

non !
pas liberer cette memoire la
bon, avant de regarder au pertes mémoires, essaye de faire fonctionner le tri

ensuite pense au pertes ...


je te conseil de prendre une feuille de brouillon et de faire des petits dessins pour te représenter les zone mémoire et les liaisons entre elles...

Citation :
376 & 377 : perte de la mémoire allouée respectivement deux lignes plus haut


Donc je dois enlever l'allocation des lignes 374 et 375 ?

Citation :
non !
pas liberer cette memoire la
bon, avant de regarder au pertes mémoires, essaye de faire fonctionner le tri

ensuite pense au pertes ...


je te conseil de prendre une feuille de brouillon et de faire des petits dessins pour te représenter les zone mémoire et les liaisons entre elles...


C'est surtout pour ça que je suis venu poster ici :jap: 

patcoll a dit :
  1. BOOL is_empty_pop (Population pop)
    

  2. {
    

  3. 	if (pop == NULL) // Teste si la population est vide
    

  4. 	  {
    

  5. 		return TRUE;
    

  6. 	  }
    

  7. 	else 
    

  8. 	  {
    

  9. 		return FALSE;
    

  10. 	  }
    

  11. }


De cette manière ça peut fonctionner ?

Salut,

tu peux remplacer ton code par :
  1. BOOL is_empty_pop (Population pop)
    

  2. {
    

  3.   return (pop == NULL)
    

  4. }

bon, la nuit porte conseil...

voici une nouvelle fonction qui rajoute une population a la fin d'une autre

  1. Population population__push_back (Population that, Population newOne)
    

  2. {
    

  3.  
  4.     if (is_empty_pop(that)) {
    

  5.         return newOne
    

  6.     } else {
    

  7.         Population fin = tail(that);
    

  8.  
  9.         fin->NextIndiv = newOne;
    

  10.     }
    

  11.     return that;
    

  12. }


et un autre qui renvoi le dernier element de la population
  1. Population tail(Population p) {
    

  2.   while ( rest(p) != NULL) { p = rest(p); }
    

  3.   return p;
    

  4. }


et maintenant le tri en lui meme
  1. /*********************************************************************
    

  2.  * Fonction qui effectue le tri rapide                                                                                *
    

  3.  *********************************************************************/
    

  4. Population quicksort(Population p)
    

  5. {
    

  6.     // Si la population est vide ou si elle ne contient qu'un seul élément, la liste est donc déjà triée donc est renvoyée tel quel
    

  7.     if (p == NULL || rest(p) == NULL ) {
    

  8.             return p;
    

  9.     } else {
    

  10.             //Déclaration d'élements "Population" permettant de faire le tri
    

  11.             Population pivot = p;
    

  12.             Population ppp = NULL, ppg = NULL;
    

  13.             Population p_parcours = rest(p);
    

  14.  
  15.             // Tant qu'on a pas parcouru toute la population à trier, on teste si la qualité de l'élément courant est inférieure ou supérieure à la qualité de l'élément pivot. Si inférieur, on la place à la fin de la liste p1, sinon à la fin de la liste p2.
    

  16.             while (p_parcours != NULL)
    

  17.                 {
    

  18.                 if ( (individu_quality(listbit_decode(head_value(p_parcours)))) < (individu_quality(listbit_decode(head_value(pivot)))) )
    

  19.                         {
    

  20.                             ppp = population__push_back(ppp, p_parcours);
    

  21.                         }
    

  22.                     else
    

  23.                         {
    

  24.                             ppg = population__push_back(ppg, p_parcours);
    

  25.                         }
    

  26.                      p_parcours = rest(p_parcours);
    

  27.                 }
    

  28.                 ppp = quicksort(ppp);
    

  29.                 ppg = quicksort(ppg);
    

  30.  
  31.                 pivot->NextIndiv = ppg;
    

  32.                 tail(ppp)->NextIndiv = pivot;
    

  33.  
  34.                 return ppp;
    

  35.         }
    

  36. }


en espérant que tu ai compris...

Re :) 

La fonction ne fait plus d'erreur de segmentation mais ne calcule pas, elel reste bloquée, j'ai mis des printf à quelques endroits pour voir ou elle bloquait, donc voici le quicksort :

  1. /**************************************
    

  2. * Fonction qui effectue le tri rapide *
    

  3. **************************************/
    

  4.  
  5. Population quicksort(Population p)
    

  6. {
    

  7. // Si la population est vide ou si elle ne contient qu'un seul élément, la liste est donc déjà triée donc est renvoyée tel quel
    

  8. 	if (p == NULL || rest(p) == NULL ) 
    

  9. 		{
    

  10. 			return p;
    

  11. 		} 
    

  12. 	else 
    

  13. 		{
    

  14. 			//Déclaration d'élements "Population" permettant de faire le tri
    

  15. 			Population pivot = p;
    

  16. 			Population ppp = NULL, ppg = NULL;
    

  17. 			Population p_parcours = rest(p);
    

  18.  
  19. 			// Tant qu'on a pas parcouru toute la population à trier, on teste si la qualité de l'élément courant est inférieure ou supérieure à la qualité de l'élément pivot. Si inférieur, on la place à la fin de la liste p1, sinon à la fin de la liste p2.
    

  20.  
  21. 			printf("Avant while\n");			
    

  22. 			while (p_parcours != NULL)
    

  23. 				{
    

  24.  
  25. 				printf("Debut while\n");					
    

  26. 				if ( (individu_quality(listbit_decode(head_value(p_parcours)))) < (individu_quality(listbit_decode(head_value(pivot)))) )
    

  27. 						{	printf("Debut if\n");
    

  28. 							ppp = concat(ppp, p_parcours);
    

  29. 						}
    

  30. 					else
    

  31. 						{
    

  32. 							ppg = concat(ppg, p_parcours);
    

  33. 						}
    

  34. 					p_parcours = rest(p_parcours);
    

  35. 				}
    

  36.  
  37. 			printf("Sortie du while\n");
    

  38. 			ppp = quicksort(ppp);
    

  39. 			ppg = quicksort(ppg);
    

  40.  
  41. 			pivot->NextIndiv = ppg;
    

  42. 			tail(ppp)->NextIndiv = pivot;
    

  43.  
  44. 			return ppp;
    

  45. 		}
    

  46. }


  1. L'individu 19 vaut 52, Sa qualite est de : -0.352539
    

  2.  
  3. L'individu 20 vaut 2, Sa qualite est de : -0.968994
    

  4.  
  5.  
  6.  **** Tri en cours **** 
    

  7. Avant while
    

  8. Debut while
    

  9. Debut while
    

  10. Debut while


Et il ne fait plus rien depuis 3 min ...

Peut être un problème dans les autres fonctions mais je ne sais pas du tout :/ 

J'ai lancé gdb, et apparement, le problème vient de la ligne 4 :

  1. Population concat (Population that, Population newOne)
    

  2. {
    

  3.  
  4. 	if (is_empty_pop(that)) {
    

  5. 		return (newOne);
    

  6. 	} else {
    

  7. 		Population fin = tail(that);
    

  8.  
  9. 		fin->NextIndiv = newOne;
    

  10. 		}
    

  11. 	return that;
    

  12. }


  1. Breakpoint 1 at 0x80489f7: file gen.c, line 349.




EDIT : apparement gdb il a des problèmes avec les if parce qeu dans quicksort la première erreur qu'il me trouve c'est dans le premier if ...

Bon j'ai réussi à avancer un peu :) 

Maintenant il sort du while etc ... mais il refait une erreur de segmentation :/ 

Les fichiers gen.h et Test.c sont les mêmes depuis le début, voici la fonction quicksort modifiée :

  1. /**************************************
    

  2. * Fonction qui effectue le tri rapide *
    

  3. **************************************/
    

  4.  
  5. Population quicksort(Population p)
    

  6. {
    

  7. // Si la population est vide ou si elle ne contient qu'un seul élément, la liste est donc déjà triée donc est renvoyée tel quel
    

  8. 	if (p == NULL || rest(p) == NULL ) 
    

  9. 		{
    

  10. 			return p;
    

  11. 		} 
    

  12. 	else 
    

  13. 		{
    

  14. 			//Déclaration d'élements "Population" permettant de faire le tri
    

  15. 			Population pivot = p;
    

  16. 			Population ppp = NULL, ppg = NULL;
    

  17. 			Population p_parcours = rest(p);
    

  18.  
  19. 			// Tant qu'on a pas parcouru toute la population à trier, on teste si la qualité de l'élément courant est inférieure ou supérieure à la qualité de l'élément pivot. Si inférieur, on la place à la fin de la liste p1, sinon à la fin de la liste p2.
    

  20.  
  21. 			printf("Avant while\n");			
    

  22. 			while (p_parcours != NULL)
    

  23. 				{
    

  24.  
  25.  
  26. 				printf("Debut while\n");					
    

  27. 					if ( (individu_quality(listbit_decode(head_value(p_parcours)))) < (individu_quality(listbit_decode(head_value(pivot)))) )
    

  28. 						{	printf("Debut if\n");
    

  29. 							ppp = insert_pop_tail(ppp, (p_parcours->people));
    

  30.  
  31. 						}
    

  32. 					else
    

  33. 						{printf("Debut else\n");
    

  34. 						ppg = insert_pop_tail(ppg, (p_parcours->people));
    

  35.  
  36. 						}
    

  37. 					p_parcours = rest(p_parcours);
    

  38. 				}
    

  39.  
  40. 			printf("Sortie du while\n");
    

  41. 			ppp = quicksort(ppp);
    

  42. 			printf("Je vais rentrer dans ppg\n");
    

  43. 			ppg = quicksort(ppg);
    

  44. 			printf("Je sors de ppg\n");
    

  45. 			pop_print(ppp);
    

  46. 			pop_print(ppg);
    

  47.  
  48.  
  49. 			pivot->NextIndiv = ppg;
    

  50. 			tail(ppp)->NextIndiv = pivot;
    

  51.  
  52. 			return ppp;
    

  53. 		}
    

  54. }


Voici ce qui est affiché lors de l'éxécution du prog :

  1. Debut else
    

  2. Sortie du while
    

  3. Je vais rentrer dans ppg
    

  4. Je sors de ppg
    

  5. L'individu 1 vaut 242, Sa qualite est de : -0.793213
    

  6.  
  7. L'individu 1 vaut 30, Sa qualite est de : -0.586182
    

  8.  
  9. Je sors de ppg
    

  10. La population entree est vide
    

  11. L'individu 1 vaut 242, Sa qualite est de : -0.793213
    

  12.  
  13. L'individu 2 vaut 228, Sa qualite est de : -0.610352
    

  14.  
  15. L'individu 3 vaut 30, Sa qualite est de : -0.586182
    

  16.  
  17. Erreur de segmentation (core dumped)
Lassé par la pub ? Créez un compte

Créer un nouveau sujet