ベクトルのオブジェクト属性別にマージソート

Question

さまざまなアルゴリズムの複雑さを比較するためのC++プロジェクトを作成します。私はサークルvector<Disque>のベクトルを持っており、私はこのベクトルを円の属性x（左のx軸=> x軸の半径）でソートしたいと思います。私はマージソートアルゴリズムを実装していますが、動作しませんし、理由を知っていません。

マージソートの実装：

/** 
* 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); 
    } 
} 

メイン：

// 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; 
} 

おかげでフランスのコードの多くと申し訳ありません:)

Answer 1

（これはあなたのアルゴリズムが正しく動作すると仮定しています）参照 "と"値によって "：あなたは値によってベクトルを渡しました。あなたはそれを変更することができるように、参照によって明確に渡す必要があります。

もしそうでなければ、あなたの関数にベクトルを渡す方法は、「値渡し」と呼ばれます。この関数はベクトルのコピーを受け取ります。このコピーを修正すると、2つのエントリを交換すると、元のベクトルは変更されません。あなたがする必要があるのは、関数をベクトルに渡して、それを変更できるようにすることです。これを行うには、vector<Disque> tableauをvector<Disque> &tableauに変更してください（fusionとtri_fusion）。値を関数に渡すための2つの方法の違いを調べる必要があります。これは非常に重要です。 tableauためindice_basとは対照的に

第二の間違いは、

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

0でtab_tmp開始にインデキシングあります。あなたは

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

このようなものに変更する必要があります私は今見ることができる唯一のミスですが、私はDisqueが何であるかを知らないと、あなたのコードをコンパイルすることはできませんので、より多くのIがあるかもしれません逃した

Answer 2

あなたtabDisque変数は、あなたのfusion() -functionに渡されます、それは返されません。それで、あなたはそれをそこに入力するのと同じ方法のままです。 1つの解決策はポインタを代わりに渡すことです。

変更するには、関数のシグネチャ：tableau変数へのすべてのアクセスを間接参照する必要があるであろう

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

。例えば。 (*tableau)[h]

と、このような参照ポインタ渡し：

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

を使用すると、関数に渡すものとの違いを認識している場合で、」