ベクトル上のメルゲートールはソートされていません

Question

私はベクトル上でマージソートしようとしていますが、私のエラーは何か分かりません。私はデスクトップテストを行いましたが、うまくいきましたが、コードを実行すると、何も並べ替えが行われず、スラッシュでベクトルが塗りつぶされる理由がわかりません。例えば

#include<iostream> 
#include<vector> 

using namespace std; 


//los vectores se pasan por referencia 
void merge(vector<int>& v, int inicio, int medio, int fin){ 
    int primera_mitad = medio-inicio+1; //para el primer arreglo 
    int segunda_mitad = fin-medio;  //para el segundo arreglo 
    //copio a cada arreglo las mitades 
    vector<int> n1; 
    vector<int> n2; 
    int i,j,k; 
    for(i=0; i<primera_mitad; i++){ 
    n1.push_back(v[inicio+i]); 
    } 
    for(j = 0; j<segunda_mitad; j++){ 
    n2.push_back(v[medio+j+1]); 
    } 
    //Ahora realizo las comparaciones para volver a ingresar al vector completo los valores 
    //de las mitades en orden. 
    i=0; 
    j=0; 
    k=inicio; 
    while(i<n1.size() && j<n2.size()){ //Mientras hayan elementos por pasar en ambos subarreglos(subvector) 
    if(n1[i]<=n2[j]){ 
     v.insert(v.begin()+k, n1[i]); 
     i++; 
    } 
    else{ 
     v.insert(v.begin()+k, n2[j]); 
     j++; 
    } 
    k++; 
    } 
    //Puede darse el caso de que un subarreglo se vacíe mas rápido que otro, por lo que pasamos directamente 
    //los demás elementos 
    while(i<n1.size()){ 
    v.insert(v.begin()+k, n1[i]); 
    i++; 
    k++; 
    } 
    while(j<n2.size()){ 
    v.insert(v.begin()+k, n2[j]); 
    j++; 
    k++; 
    } 
} 

void merge_sort(vector<int>& v, int inicio, int fin){ 
    if(inicio<fin){ 
    int medio = ((fin+inicio)/2); 
    merge_sort(v, inicio, medio); 
    merge_sort(v, medio+1, fin); 
    merge(v, inicio, medio, fin); 
    } 
} 


void print(vector<int>& v){ 
    cout<<endl; 
    int tam = v.size(); 
    for(int i = 0; i<tam; i++){ 
    cout<<i+1<<".\t"<<v[i]<<"\n"; 
    } 
} 

int main() { 
    cout<<"----------------MERGE SORT----------------\n\n"; 
    cout<<"\nPlease, fill the vector: \n\n"; 
    int a; 
    bool response = true; 
    vector<int> v; 
    while(response){ 
     cout<<"\nEnter your number: "; 
     cin>>a; 
     v.push_back(a); 
     cout<<"Another?(1/0): "; 
     cin>>response; 
     cout<<endl; 
    } 
    int tam = v.size(); 
    merge_sort(v, 0, tam-1); 
    print(v); 
    return 0; 
} 

、私は、入力として、この数字を入れて：ここで

はコードである

1 4 10 5 6 

プログラムは私にこの出力を与える：

1. 1 
2. 1 
3. 1 
4. 10 
5. 10 
6. 1 
7. 1 
8. 10 
9. 1 
10. 10 
11. 1 
12. 10 
13. 1 
14. 10 
15. 4 
16. 5 
17. 6 

希望します助けて。ありがとう。

Answer 1

最初にリストからコピーするのではなく、現在地を追跡して新しい出力リストにマージするだけです。完了したら、古い値を新しい値に置き換えます。 v.insert（）は使わないでください。 V [IDX] =出力[IDX2]

OR

あなたは二つの入力のリストを維持することができますが、あなたはまだリスト内の値を交換する必要があります。 v [idx ++] =値。 idxは最初のリストの先頭から始める必要があります。

どちらの場合でも、インデックスの代わりにイテレータを使用すると思います。この方法でベクトルを渡すのを避けることができます。マージソートを作成するために構造体にランダムアクセスする必要はありません。これはstd :: listで動作するはずです。 ++ iterを使用して要素をトラバースすることができます。