CODEWITHSUNDEEP
c++vectormergesort
Mattasse
Mattasse

Reputation: 1161

Merge sort by object attribute in vector

I make a c++ project to compare different algorithm complexity. I have a vector of Circle vector<Disque> and i would like to sort this vector by attribute x of circle (x-axis the most in left => x-axis-radius). I've implement merge-sort algorithm but doesn't work and dont know why.

Merge sort implementation : 

/**
* Méthode qui permet de fusionner les tableaux qui ont été séparés afin de trier le tableau final
* @param indice_bas
* @param milieu
* @param indice_haut
* @param taille
*/
void fusion(int indice_bas, int milieu, int indice_haut, vector<Disque> tableau) {
    // Déclaration de différents indices pour la fusion
    int h,i,j,k;
    // Déclaration du tableau intérmediaire qui permet de stocké les disques du tableau
    vector<Disque> tab_tmp;
    // Initialisation des indices
    h = indice_bas;
    i = indice_bas;
    j = milieu+1;

    // Tant que nous avons pas trié l'ensemble du tableau
    while((h <= milieu) && (j <= indice_haut)) {
        // Si la valeurs de gauche est plus petite que celle de droite
        if((tableau[h].getPoint().getX() - tableau[h].getRayon()) <= (tableau[j].getPoint().getX() - tableau[j].getRayon())) {
            // On insère la valeur de gauche et on incrémente l'indice h
            tab_tmp.push_back(tableau[h]);
            h++;
        } else {
            // Sinon on interverti les valeurs du tableau afin de les remettrent dans l'ordre et on incrémente l'indice j
            tab_tmp.push_back(tableau[j]);
            j++;
        }
        // Incrémentation de i car tab_tmp[i] possède désormais une valeur
        i++;
    }

    // Si il reste des valeurs à insérer dans le tableau temporaire, on les insère suivant si elles sont dans le tableau de droite ou de gauche
    if(h > milieu) {
        // Boucle qui permet d'insérer les valeurs restantes
        for(k = j; k <= indice_haut; k++)
        {
            tab_tmp.push_back(tableau[k]);
            i++;
        }
    } else {
        // Boucle qui permet d'insérer les valeurs restantes
        for(k = h; k <= milieu; k++) {
            tab_tmp.push_back(tableau[k]);
            i++;
        }
    }

    // On replace les valeurs une à une dans le tableau que nous avons trié
    for(k = indice_bas; k <= indice_haut; k++){
        tableau[k] = tab_tmp[k];
    }
}

/**
 * Méthode tri fusion qui permet de trier les abscisse du point central d'un disque.
 * Choix de cet algorithme car la complexité est en n log n
 * @param indice_bas
 * @param indice_haut
 */
void tri_fusion(int indice_bas, int indice_haut, vector<Disque> tableau, int taille){
    // On déclare un indice qui correspond au milieu du tableau à trier pour effectuer un split
    int milieu;
    if(indice_bas < indice_haut) {
        // Calcul du milieu du tableau
        milieu = indice_bas + (indice_haut - indice_bas) / 2;
        // On appel récursivement la méthode de tri fusion jusqu'à la division de tous les tableaux
        tri_fusion(indice_bas, milieu, tableau, taille);
        tri_fusion(milieu + 1, indice_haut, tableau, taille);
        fusion(indice_bas, milieu, indice_haut, tableau);
    }
}

Main : 

// Fonction main qui est le point d'entrée du programme
int main(int argc, const char * argv[]) {
    // Permet de générer plus d'aléa pour la création des disques
    srand((unsigned)time(NULL));
    // On crée quelques disques pour essayer les algos
    vector<Disque> tabDisque;
    for (int i=0; i < 10; ++i) {
        tabDisque.push_back(Disque(rand() % 10 + 1, Point(rand() % 30 + 1, rand() % 30 + 1)));
    }

    // On récupère la taille du vector
    int const taille = (const int)tabDisque.size();

    tri_fusion(0, taille-1, tabDisque, taille);

    for (int z = 0; z < taille ; z++) {
        cout << tabDisque[z].getPoint().getX() - tabDisque[z].getRayon() << " ";
    }
    return 0;
}

Thanks a lot and sorry for the french code :)

Upvotes: 1

Views: 375

Answers (2)

Shaomada
Shaomada

Reputation: 26

If you are aware of the difference between passing things to a function "by reference" and "by value": You passed your vector by value, you should clearly pass it by reference so you can modify it.

If not: The way you pass you vector to your function right now is called passing "by value". The function will receive a copy of the vector. Now if you modify this copy, say by swapping two entries, the original vector will be unchanged. What you need to do is pass the function a reference to the vector so you can modify it. To do so, change vector<Disque> tableau to vector<Disque> &tableau both in fusion and tri_fusion. You should look up the difference between these two ways to pass values to functions, it's quite important.

A second mistake is

for(k = indice_bas; k <= indice_haut; k++){
  tableau[k] = tab_tmp[k];
}

The indexing in tab_tmp starts at 0, as opposed to indice_bas for tableau. You need to change this to something like

for(k = 0; k <= indice_haut-indice_bas; k++){
  tableau[k+indice_bas] = tab_tmp[k];
}

This are the only mistakes I can see right now, but I can't compile your code as I don't know what Disque is, so there might be more I have missed.

Upvotes: 1

DuKes0mE
DuKes0mE

Reputation: 1131

Your variable tabDisque gets passed to your fusion()-function, but it does not get returned. So it stays the same way how you input it there. One solution would be passing pointers instead.

Change the signature of your function to:

void fusion(int indice_bas, int milieu, int indice_haut, vector<Disque> *tableau)

Any access to tableau variable would need to be dereferenced. E.g. (*tableau)[h]

and pass a reference pointer like this:

tri_fusion(0, taille-1, &tabDisque, taille);

(This is assuming your algorithm works correctly)

Upvotes: 1

Related Questions