Compter le nombre de comparaisons pour tri rapide

bonjour,

ton programme exécute sans doute une instruction pour faire la comparaison.

tu peux probablement incrémenter un compteur chaque fois que cette instruction est exécutée.

Voici mon code

void echanger(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int t[], int debut, int fin) {
    int valeur_pivot = t[fin];
    int indice_pivot = debut;
    int i;
    for (i = debut;i < fin; i++){
      if (t[i] <= valeur_pivot){
        echanger(&t[i], &t[indice_pivot]);
        indice_pivot += 1;
      }
    }
    echanger(&t[fin], &t[indice_pivot]);
    return indice_pivot;
}

void tri_segmentation(int t[], int debut, int fin) {
  int pivot;
  if (fin > debut) {
    pivot = partition(t, debut, fin);
    tri_segmentation(t, debut, pivot - 1);
    tri_segmentation(t, pivot + 1, fin);
  }
}

J'ajoute un compteur dans ma boucle

if (t[i] <= valeur_pivot)

? 

J'ai fait:

int partition(int t[], int debut, int fin){
    int valeur_pivot = t[fin];
    int indice_pivot = debut;
    int i;
    int nb_comp = 0;
    for(i = debut; i < fin; i++){
      if (t[i] <= valeur_pivot){
        echanger(&t[i], &t[indice_pivot]);
        indice_pivot += 1;
        nb_compt++;
      }
    }
    echanger(&t[fin], &t[indice_pivot]);
    return indice_pivot;
}

On compte le nombre de comparaisons dans partition et je veux que dans tri segmentation ca soit le nombre de comparaison a droite et a gauche comme ca on aura le nombre total de comparaison dand tri rapide

Pour compter combien de comparaison on fait,dans if car on a une comparaison  c'est a dire 

t[i] <= valeur_pivot

Oui, je comprends le code vu que c'est moi qui l'ai écris

Voulez-vous que je détaille ce que fait le code a chaque itération ou bien c'est pas nécessaire

Salut Theo_0055,

Si tu incrémentes dans les accolades de la condition if, tu ne comptes pas le nombre de comparaisons effectuées, mais seulement le nombre de fois où la comparaison effectuée a été évaluée à "vrai".

Or, une comparaison évaluée à "faux" est aussi une comparaison faite, à compter.

En fait ... à chaque itération de la boucle, dans laquelle se trouve cette instruction if, tu fais cette comparaison... non ?

Vois-tu plus clairement maintenant la solution simple vers laquelle yg_be essaye de te guider ?

Si tu avais un code plus complexe, et tu voulais t'assurer de compter le nombre de fois que la condition du if est évaluée, tu peux aussi compter dans les parenthèses de ta condition if. Comme ceci :

if (nb_compt++, t[i]<=valeur_pivot) {

Cela n'affecte pas la comparaison, car avec l'opérateur virgule, seule la dernière instruction est évaluée pour les besoins du test. Tu es sûr d'être "au plus près" du test exécuté.

Mais, en l'occurrence, tu n'as pas besoin de cette astuce :-)

Si je connais cette astuce sauf que je savais pas si je devrais l'utilser ici ou pas

Le fait d'écrire cela compte le nombre de comparaisons qu'on q'importe si le 

 
t[i]<=valeur_pivot est vrai ou faux,okkk j'ai compris

@yg_be je vois donc pourquoi je dois compter hors du if,okk

Ensuite,il se pose un autre probléme,vu que ma fonction partition il renvoie l'indice du pivot,je peux pas renvoyer en plus le nombre de comparaison

En fait dans tri rapide ,je veux que partition me donne le nombre de comparasions du tableau a gauche du pivot et a droite et je veux additionner les 2 pour avoir le nombre totale de comparasions dans tri rapide,quel astuce utiliser pour cela?

Dal a deja donne la solution pour partition

Si vous voulez hors du if sans utiliser l’astuce,on fait:

int partition(int t[],int debut,int fin){
    int valeur_pivot=t[fin];
    int indice_pivot=debut;
    int i;int nb_comp=0;
    for(i=debut;i< fin;i++){
      nb_compt++;
      if (t[i]<=valeur_pivot){
        echanger(&t[i], &t[indice_pivot]);
        indice_pivot+=1;
        nb_compt++
      }
    }
    echanger(&t[fin], &t[indice_pivot]);
    printf(« le nombre de comparaison est %d »,nb_compt);
    return indice_pivot;
}

Une erreur dans la fonction partition? Ou bien la msniere dont je compte la comparaison?

Sans utilise l'astuce nb_compt if(nb_compt,...)

Mon code le nb_compt je l'ai mis dans mon for et pas dans la boucle du if donc je compte en dehors du if,je vois pas pourquoi vous dites je compte aussi dans le if

Ah desole je suis trompé ,j'ai oublie de effacer en copiant coller le code le nb_compt dans le if

maintenant que j'ai montré comment compter le nombre de comparasion dans la fonction partition,comment je dois m'y prendre dans la fonction tri rapide svp

En fait comme ce que j'ai dit je suis bloqué

sachant que ma fonction partition me renvoie l'indice du pivot,je peux pas renvoyer aussi le nombre de comparaisons car dans mon exo on n'a dit ne pas changer les entrees et sorties des fonctions

du coup lorsque j'appelle cette fonction dans tri rapide,je perds les info sur le nombre de comparaisons,je sais pas comment le stocker

Bonjour,

Le plus simple est de passer l'adresse d'un compteur à ta fonction partition et de définir une fonction compare qui prend en paramètre les deux valeurs à comparer et l'adresse du compteur.

#include <stdbool.h>

bool compare(int a, int b, unsigned *pnum_comparaisons) {
  *pnum_comparaisons++; // On incrémente le compteur
  return a <= b;
}


size_t partition(int t[], size_t debut, size_t fin, unsigned *pnum_comparaisons) {
  *pnum_comparaisons = 0; // Initialisation du compteur
  ...
  // if (t[i] <= valeur_pivot) {
  if (compare(t[i], valeur_pivot, pnum_comparaisons)) {
  ...
}

int main() {
  unsigned num_comparaison;
  ...
  partition(t, debut, fin, &num_comparaison);
  ...
}

Bonne chance

En fait j'ai juste pas le droit de modifier ma fonction tri rapide

bon le tri rapide de l'exo il est de la forme:int tab[],int n et la fonction tri rapide que j'ai donne ici dans ce forum est en quelque sorte un tri_rapide_rec aue je peux appeler dans ma fonction tri_rapide(int tab[],int n) .Ca ce n'est pas un probleme

partition est une fonction auxiliaire utilise par moi pour simplifier le code plutot que d'ecrire le code tri rapide d'un coup

Ah ok je vois en fait pas besoin de compter faire a gauche et a droite 

Donc on a:

void echanger(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}


bool compare(int a, int b, unsigned *pnum_comparaisons) {
  *pnum_comparaisons++; // On incrémente le compteur
  return a <= b;
}

size_t partition(int t[], size_t debut, size_t fin, unsigned *pnum_comparaisons) {
  *pnum_comparaisons = 0; // Initialisation du compteur
 
    int valeur_pivot = t[fin];
    int indice_pivot = debut;
    int i;
    for (i = debut;i < fin; i++){
      if (compare(t[i], valeur_pivot, pnum_comparaisons)) {
        echanger(&t[i], &t[indice_pivot]);
        indice_pivot += 1;
      }
    }
    echanger(&t[fin], &t[indice_pivot]);
    return indice_pivot;
}



void tri_segmentation(int t[], int debut, int fin) {
  int pivot;
  unsigned num_comparaison;
  if (fin > debut) {
    pivot = partition(t, debut, fin, &num_comparaison);
    tri_segmentation(t, debut, pivot - 1);
    tri_segmentation(t, pivot + 1, fin);
  }
}