6 Replies - 268 Views - Last Post: 08 February 2013 - 01:51 PM Rate Topic: -----

#1 eyerandom  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 07-February 13

Mergesort c++ problem

Posted 07 February 2013 - 12:20 PM

Hi, I'm doing an assignment where I am supposed to implement a merge sort algorithm (shown below). Even though everything compiles, the elements are not actually sorted. I have been looking around for about an hour now and can't seem to figure out what is wrong with my code. Any input is greatly appreciated!


 void mergesort(vector<int> &data) {
  // implement me
	vector<int> left;
	vector<int> right;
	
	if (data.size() <= 1) {
		return;
	}
	else {
		int mid = (data.size()/2);
		
		
		for (int i = 0; i < mid; ++i) 
			left.push_back(data[i]);
		for (unsigned int i = mid; i < data.size(); i++) 
			right.push_back(data[i]);
	
		mergesort(left);
		mergesort(right);
		merge(left, right);

}
}

vector<int> merge(vector<int> &left, vector<int> &right) {
	vector<int> result;
	unsigned left_it = 0, right_it = 0;
	
	while (left_it <left.size() && right_it < right.size()) {
		if (left[left_it] < right[right_it]) { 
			result.push_back(left[left_it]);
			left_it++;
		}
		else {
			result.push_back(right[right_it]);
			right_it++;
		}
	}
	
	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;
		
  // implement me

} 


Is This A Good Question/Topic? 0
  • +

Replies To: Mergesort c++ problem

#2 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: -4
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Mergesort c++ problem

Posted 07 February 2013 - 01:20 PM

Well, you haven't actually implemented the merge sort. Are you familiar with the actual algorithm?
Was This Post Helpful? 0
  • +
  • -

#3 jimblumberg  Icon User is online

  • member icon


Reputation: 3845
  • View blog
  • Posts: 11,737
  • Joined: 25-December 09

Re: Mergesort c++ problem

Posted 07 February 2013 - 02:23 PM

Here is a link that explains how the merge sort works. Merge Sort Algroithm.

Jim
Was This Post Helpful? 0
  • +
  • -

#4 eyerandom  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 07-February 13

Re: Mergesort c++ problem

Posted 07 February 2013 - 03:27 PM

View PostButchDean, on 07 February 2013 - 01:20 PM, said:

Well, you haven't actually implemented the merge sort. Are you familiar with the actual algorithm?


What do you mean by "implement?" I have a driver that implements it if that is what you mean. I think that there is a logic error that I am not seeing.
Was This Post Helpful? 0
  • +
  • -

#5 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: -4
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Mergesort c++ problem

Posted 07 February 2013 - 04:21 PM

If it isn't doing what you expect then you haven't implemented it. Just by eyeballing your code I can see it doesn't look right.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2013
  • View blog
  • Posts: 3,038
  • Joined: 21-June 11

Re: Mergesort c++ problem

Posted 07 February 2013 - 05:41 PM

Your merge_sort function is void and takes its argument by non-const reference. This suggests that it should modify the given vector in-place. But it never does that. It splits the vector into two halves and then it never does anything with the vector again. So the original vector remains unchanged. You should either modify the vector, or change the function to return a new sorted vector instead of being void. If you choose the latter, you need to change your recursive calls to use the return values.

Also you're never actually using the return value of your merge function. Just calling the function won't do anything, you need to use its return value. Since the function doesn't modify its argument, getting its return value is the only reason to call it.

On a style note the arguments to merge should be const references because, as I mentioned, it doesn't modify its argument.
Was This Post Helpful? 1
  • +
  • -

#7 eyerandom  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 07-February 13

Re: Mergesort c++ problem

Posted 08 February 2013 - 01:51 PM

derp. had to set data = merge(left, right). Thanks for the input!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1