Question

J'essaye d'implémenter une fonction de tri de fusion et j'obtiens une erreur de compilateur qui indique "aucune correspondance pour 'operator ='" Elle se produit sur mon assignation récursive de left_list = mergesort (left_list) et la même erreur dans la ligne suivante en utilisant right_list.

Il se compile correctement si je retire l'affectation et ai juste mergesort (left_list) mais alors il ne trient pas correctement. Je pensais que la façon dont je l'ai maintenant devrait trier correctement, mais étant donné que ce n'est pas le cas, l'erreur a quelque chose à voir avec ces lignes ou ailleurs dans la fonction mergesort() ou merge().

Toute aide serait appréciée.

void mergesort(vector<int> &data) { 

vector<int> left_list; 
vector<int> right_list; 

if (data.size() <= 1) { 
    return; 
} 

// creates a middle point to separate into 2 sub lists 
int middle = (data.size()/2); 

// create a list of elements to the left of middle 
for (int i = 0; i < middle; i++) { 
    left_list.push_back(data[i]); 
} 

// create a list of elements to the right of middle 
for (unsigned int i = middle; i < data.size(); i++) { 
    right_list.push_back(data[i]); 
} 

// break down the sub lists until they are of size 1 
left_list = mergesort(left_list); 
right_list = mergesort(right_list); 

// merge the sublists in the correct order 
merge(left_list, right_list); 



} 

vector<int> merge(vector<int> &left, vector<int> &right) { 

vector<int> result; 

unsigned left_it = 0; 
unsigned right_it = 0; 

while(left_it < left.size() && right_it < right.size()) { 


    // the smaller value is put into the result vector 
    if(left[left_it] < right[right_it]) { 

     result.push_back(left[left_it]); 
     left_it++; 
    } 
    else 
    { 
     result.push_back(right[right_it]); 
     right_it++; 
    } 
} 

// Put the rest of the data from both vectors onto result 
while(left_it < left.size()) { 

    result.push_back(left[left_it]); 
    left_it++; 
} 

while(right_it < right.size()) { 

    result.push_back(right[right_it]); 
    right_it++; 
} 

return result; 

} 

Answer 1

Vous avez du code qui tente d'accepter une valeur de retour de la fonction mergesort. Si c'est ce que vous voulez, ma réponse originale répond à cette question. Cependant, si mergesort est supposé mettre à jour le paramètre d'entrée avec le résultat trié, alors il n'a pas besoin de retourner de valeur, et void est correct. Ensuite, les instructions d'affectation obtenant son résultat de retour sont erronées et doivent être modifiées.

mergesort(left_list); 
mergesort(right_list); 

Cependant, l'appel à merge doit affecter le résultat au paramètre d'entrée.

data = merge(left_list, right_list); 

Ma réponse originale suit:

Vous devez changer votre fonction mergesort pour retourner le même type que merge retours.

vector<int> mergesort(vector<int> &data) { 

Vous devez alors mettre à jour la mise en œuvre mergesort de telle sorte que la première instruction return renvoie le paramètre d'entrée:

return data; 

La dernière déclaration devrait être modifiée pour renvoyer le résultat:

return merge(left_list, right_list); 

Je n'ai pas regardé la mise en œuvre de l'algorithme lui-même.