C++ - Merge-Sortierung nach Wert übergeben

Question

Ich versuche, den Merge-Sort-Algorithmus rekursiv zu implementieren, indem ich nur einen Vektorwert an die Funktion übergebe (kein linker oder rechter Index). Die while-Schleife im folgenden Code funktioniert, wenn die zu sortierende Liste als Zeiger void merge_sort_array(int* v, int l, int r) oder Referenz void merge_sort_ref(vector<int>& v, int l, int r) übergeben wird, aber ich kann nicht für das Leben von mir verstehen, warum der folgende Code meine Liste nicht richtig sortiert. Ich habe das Gefühl, dass es etwas mit den Startwerten von i, j, k oder den Grenzen innerhalb meiner while-Schleife zu tun hat, aber ich habe alles versucht, was für mich Sinn ergibt und es nicht herausfinden kann.

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include <vector> 
#include <algorithm> 

using namespace std; 
vector<int> merge_sort_value(vector<int> v) { 
    int n = v.size(); 
    if(n == 1){ 
     return v; 
    } 
    else{ 
     int m = n/2; 
     vector<int> v1(v.begin(), v.begin()+m); 
     vector<int> v2(v.begin()+m, v.begin()+n); 
     merge_sort_value(v1); 
     merge_sort_value(v2); 
     vector<int> tmp(v.begin(), v.begin()+m); 
     int i = 0; 
     int j = m; 
     int k = 0; 
     while((i < m) or (j < n)){ 
      if(i == m){ 
       v[k] = v[j]; 
       j +=1; 
      } 
      else if((j == n) or (tmp[i] < v[j])){ 
       v[k] = tmp[i]; 
       i+=1; 
      } 
      else{ 
       v[k] = v[j]; 
       j+=1; 
      } 
      k+=1; 
      # print output for debugging 
      for(auto x = v.begin(); x != v.end(); ++x) 
       cout << *x << " "; 
      cout << "" << endl; 
      cout << i << "\t"<< j << "\t" << k << endl; 
     } 
     return v; 
    } 
} 

int main(int argc, char** argv) { 
    vector<int> v(10); 

    for(int i=0; i < 10; ++i) 
     v[i] = rand() % 100; 

    v = merge_sort_value(v); 
    return 0; 
} 

ich ein Beispiel für die Ausgabe als Referenz unten aufgenommen haben:

28 28 
0 2 1 
28 80 
1 2 2 
21 21 
0 2 1 
21 92 
1 2 2 
14 92 21 
1 1 1 
14 92 21 
1 2 2 
14 92 21 
1 3 3 
14 28 14 92 21 
0 3 1 
14 80 14 92 21 
1 3 2 
14 80 28 92 21 
2 3 3 
14 80 28 92 21 
2 4 4 
14 80 28 92 21 
2 5 5 
21 57 
1 1 1 
21 57 
1 2 2 
78 83 
1 1 1 
78 83 
1 2 2 
78 78 83 
0 2 1 
78 83 83 
0 3 2 
78 83 96 
1 3 3 
21 57 96 78 83 
1 2 1 
21 57 96 78 83 
2 2 2 
21 57 96 78 83 
2 3 3 
21 57 96 78 83 
2 4 4 
21 57 96 78 83 
2 5 5 
21 28 14 92 21 21 57 96 78 83 
0 6 1 
21 57 14 92 21 21 57 96 78 83 
0 7 2 
21 57 80 92 21 21 57 96 78 83 
1 7 3 
21 57 80 28 21 21 57 96 78 83 
2 7 4 
21 57 80 28 14 21 57 96 78 83 
3 7 5 
21 57 80 28 14 92 57 96 78 83 
4 7 6 
21 57 80 28 14 92 21 96 78 83 
5 7 7 
21 57 80 28 14 92 21 96 78 83 
5 8 8 
21 57 80 28 14 92 21 96 78 83 
5 9 9 
21 57 80 28 14 92 21 96 78 83 
5 10 10 

Vielen Dank, wird jede Hilfe sehr dankbar!

Answer 1

, nachdem Sie es bewerten den Code scheint Sie Fehler im Algorithmus es selbst machst und in C++ als Sprache, so dass ich Ihren Algorithmus bearbeitet haben mehr ordentlich und besser lesbar Algorithmus sein ich einen Teil des Codes erklären

-Code

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include <vector> 
#include <algorithm> 

using namespace std; 
vector<int> merge_sort_value(vector<int> v) { 
    int n = v.size(); 
    if(n == 1){ 
    return v; 
    } 
    else{ 
    int m = n/2; 
    vector<int> v1(v.begin(), v.begin()+m); 
    vector<int> v2(v.begin()+m, v.begin()+n); 
    v1 = merge_sort_value(v1); /* passing by value will left v1 with no sorting so you need to copy from the returned 
    object */ 
    v2 = merge_sort_value(v2); 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    const size_t left_vecS = v1.size(); 
    const size_t right_vecS = v2.size(); 

    while (i<left_vecS&&j<right_vecS) { // we must keep i (AND) j valid 
     if (v1[i] < v2[j]) 
     v[k++] = v1[i++]; 

     else 
     v[k++] = v2[j++]; 
    } 

     while(i<left_vecS) // if we sorted v2 then what insert the rest of v1 in v as what kept from v1 will be sorted 
     v[k++] = v1[i++]; 


     while(j<right_vecS) 
     v[k++] = v2[j++]; 
    } 
    return v; 
    } 


int main(int argc, char** argv) { 
    vector<int> v(10); 
    std::vector<int> x; 

    for(int i=0; i < 10; ++i) 
    v[i] = rand() % 100; 

    v = merge_sort_value(v); 

    for(auto&i:v) 
    std::cout << i << std::endl; 

    return 0; 
} 

1- ich werde in der Sortierfunktion des Druck befreien, so halten wir den Code sauber

2- Der erste Fehler, den Sie auf der Sprachstufe gemacht haben, ist, dass Sie das zurückgegebene sortierte Vektorobjekt nicht von merge_sort_value in die Vektoren kopiert haben (ich habe das im Code in einem Kommentar erwähnt), also ist das das erste Sache im Auge zu halten

3- die Logik Teil des Algorithmus war mir nicht klar, weil ich nicht sehen, wie Sie das Sortieren speziell, dass ein Teil else if ((j == n) or (tmp[i] < v[j])) { v[k] = tmp[i]; i += 1; }

wie Sie vergleichen unsortiert Untervektor zu einem anderen unsortierten Vektor und du gibst es wieder unsortierten Wert (Sie müssen v1 gegen v2 vergleichen) die ganze Logik ist vermisst, ich denke, Sie brauchen um es zu überprüfen

auf jeden Fall hoffe ich, dass geholfen