Tri de fusion C++ passé par valeur

Question

J'essaye d'implémenter récursivement l'algorithme de tri de fusion en passant seulement une valeur vectorielle à la fonction (pas d'index gauche ou droit). La boucle while dans le code suivant fonctionne lorsque la liste à trier est passée en tant que pointeur void merge_sort_array(int* v, int l, int r) ou référence void merge_sort_ref(vector<int>& v, int l, int r) mais je ne peux pas pour la vie de moi comprendre pourquoi le code suivant ne triera pas correctement ma liste. J'ai le sentiment que c'est quelque chose à voir avec soit les valeurs de départ de i, j, k ou les limites de ma boucle while mais j'ai essayé tout ce qui a du sens pour moi et je n'arrive pas à le comprendre.

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

J'ai inclus une sortie de l'échantillon de référence ci-dessous:

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 

Merci, toute aide est grandement appréciée!

Answer 1

après avoir examiné vous le code, il semble que vous faire des erreurs dans l'algorithme elle-même et en C++ comme langage pour que je l'ai modifié votre algorithme pour être plus algorithme propre et plus facile à lire, je vais vous expliquer une partie du code

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- je me débarrasser de l'impression dans la fonction de tri nous conservons donc le code propre

2- La première erreur que vous avez faite au niveau du langage est que vous n'avez pas copié l'objet vectoriel trié retourné de merge_sort_value vers les vecteurs (je l'ai mentionné dans le code dans un commentaire), donc c'est le premier chose à garder à l'esprit

3- la partie logique de l'algorithme n'a pas été clair pour moi parce que je ne vois pas comment vous le tri spécialement cette partie else if ((j == n) or (tmp[i] < v[j])) { v[k] = tmp[i]; i += 1; }

comme vous comparez unsorted sous-vecteur à un autre vecteur non trié et vous donnez encore une valeur non triée (vous devez comparer v1 contre v2) toute la logique est ratée, je pense que vous avez besoin pour l'examiner

de toute façon j'espère que cela a aidé