Informatique

Bonjour, je cherche à créer une fonction qui partitionne une suite de valeur en mémoire autour d'un pivot pour ensuite implanter la fonction standard quick_sort. Mais mes premiers tests m'affichent des valeurs inattendues (de très grands nombres ou des 0).

J'ai vraiment du mal à repérer mon erreur, merci d'avance pour vos réponses

Voici mon code pour la fonction:

void *partition_pivot(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *)) {
  if (size == 0 || nmemb == 0) {
    return NULL;
  }
  char *k = (char *)base + (nmemb - 1) * size;
  char *p = (char *)base;
  char *q = (char *)base;
  while (q < k) {
    if (compar(q, k) < 0) {
      mem_swap(p, q, size);
      ++p;
    }
    ++q;
  }
  mem_swap(p, k, size);
  return p;
}

c'est pas ++p que tu veux. c'est p+=size;

PS: Qu'est ce que c'est moche du C.

merci beaucoup ! ça a l'air de marcher
Mais dans ce cas pourquoi pas q += size ?

bah aussi

Oui, c'est logique , c'est juste que bizarrement ça semblait fonctionner sans avoir modifié l'affecation à q .
Enfin bref, du coup j'en suis au quick_sort, mais je n'arrive pas à déterminer ce que j'envoie comme nmemb dans les 2 appels récursifs :

void quick_sort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *)) {
  char *j = (char *)base;
  char *k = (char *)base + (nmemb - 1) * size;
  char *p;
  while (j < k) {
    p = partition_pivot(j, nmemb, size, compar);
    printf("%p\n", p);
    if (p - j < k - p) {
      quick_sort(j, ???, size, compar);
      j = p + size;
    }else{
      quick_sort(p + size, ???, size, compar);
      k = p - size;
    }
  }
}

Naturellement je pense à (p - j) / size et (k - p) / size mais apparemment ce n'est pas ça (ma boucle tourne à l'infini) à moins que je me trompe autre part...

deroule un exemple a la main, c'est ce qu'il y a de plus simple pour trouver ce genre de truc.

Alors là par contre j'ai un vrai problème, j'ai testé le retour de la fonction de partition avec un:
printf("%d", *p)
juste avant de retourner p, et en fait la fonction renvoie la plus grande valeur du tableau, et non le pivot

fais attention. les types dans printf ne matchent pas, *p c'est un char, et %d ca denote un entier. deroule tes fonctions a la main et tu devrais voir ce qu'il se passe.

Bon je crois que je vais abandonner , j'ai tout essayé, y compris dérouler à la main (à la main ça semble fonctionner) mais plus le temps passe et moins j'arrive à réfléchir, c'est horrible
Quoi que je fasse, le programme ne s'arrête pas, j'ai l"impression de passer à côté d'un trucs grotesque ça m'énerve tellement ...