Jump to content
  • Advertisement
Sign in to follow this  
Gullanian

merge sort help (C++)

This topic is 4326 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi guys, I've written a merge sort that doesn't *quite* work, if anyone can assist me trying to find where it fails, it would be most helpful. Sorry for repost, accidently posted this in game discussion. This is the structure of the thing to be sorted
struct gameRoom
{
	int ID;
	string roomsName;
};


This sets up the test data
int _tmain(int argc, _TCHAR* argv[])
{
	// List of gamerooms
	vector<gameRoom> gameRooms;

	// Create test instances
	gameRoom gr;
	gr.ID = 2;
	gameRooms.push_back(gr);
	gr.ID = 5;
	gameRooms.push_back(gr);
	gr.ID = 3;
	gameRooms.push_back(gr);
	gr.ID = 1;
	gameRooms.push_back(gr);
	//gr.ID = 8;
	//gameRooms.push_back(gr);
	cout<<"Loaded..."<<endl<<endl;

	// Begin to merge sort the list
	mergeSort(&gameRooms, DESC, 0, gameRooms.size() - 1);

	// Print out the game rooms
	printRooms(&gameRooms);

	return 0;
}


This is the recursive function mergesort
// Merge two sets of data
void mergeSort(vector<gameRoom>* gameRooms, bool sortType, int startEl, int endEl)
{

	vector<gameRoom> mResult;

	// Solitary element
	if (endEl - startEl == 0)
	{

	}
	// More than one element
	else
	{
		int middleElement = (endEl + startEl) / 2;

		// Merge the split
		mergeSort(gameRooms, sortType, startEl, middleElement);
		mergeSort(gameRooms, sortType, middleElement + 1, endEl);

		// Merge
		mResult = merge(gameRooms, startEl, middleElement, middleElement + 1, endEl, sortType);

		// Copy result into set
		int startElPointer = startEl;
		for (int i = 0; i < mResult.size(); i++)
		{
			gameRooms->at(startElPointer) = mResult.at(i);
			startElPointer++;
		}
	}
}


This function sorts two presorted lists
// Merge left and right lists
vector<gameRoom> merge(vector<gameRoom>* gameRooms, int leftSetStart, int leftSetEnd, int rightSetStart, int rightSetEnd, bool sortType)
{
	// Get number of elements in each list
	int leftSetPointer = leftSetStart;
	int rightSetPointer = rightSetStart;

	// Result set
	vector<gameRoom> returnList;

	// Loop through and merge the two sets
	do
	{
		// Type of sort
		switch (sortType)
		{
			// Sorting ascending
			case (ASC):

				// Want smallest one
				if (gameRooms->at(leftSetPointer).ID < gameRooms->at(rightSetPointer).ID)
				{
					returnList.push_back(gameRooms->at(leftSetPointer));
					leftSetPointer ++;
				} else
				{
					returnList.push_back(gameRooms->at(rightSetPointer));
					rightSetPointer ++;
				}

				break;

			// Sorting descending
			case (DESC):

				// Want biggest one
				if (gameRooms->at(leftSetPointer).ID > gameRooms->at(rightSetPointer).ID)
				{
					returnList.push_back(gameRooms->at(leftSetPointer));
					leftSetPointer ++;
				} else
				{
					returnList.push_back(gameRooms->at(rightSetPointer));
					rightSetPointer ++;
				}

				break;
		}

	} while(leftSetPointer != leftSetEnd && rightSetPointer != rightSetEnd);

	// Append remaining elements to results
	if (leftSetPointer != leftSetEnd)
	{
		for(leftSetPointer; leftSetPointer < leftSetEnd; leftSetPointer ++)
		{
			returnList.push_back(gameRooms->at(leftSetPointer));
			leftSetPointer ++;	
		}
	}
	else if (rightSetPointer != rightSetEnd)
	{
		for(rightSetPointer; rightSetPointer < rightSetEnd; rightSetPointer ++)
		{
			returnList.push_back(gameRooms->at(rightSetPointer));
			rightSetPointer ++;	
		}
	}

	for (int i = 0; i < returnList.size(); i++)
	{
		cout<<returnList.at(i).ID<<endl;
	}

	// Return results
	return returnList;
}


So the test data is: 2 5 3 1 And it prints: 5 3 3 1 Thanks for any help with this!

Share this post


Link to post
Share on other sites
Advertisement
Any particular reason for not using std::stable_sort (which is typically implemented with merge sort) or std::sort? since you're already using parts of the C++ standard library that is why I ask.

Share this post


Link to post
Share on other sites
I second what snk_kid said too. Your problem however lies in the confusing of where to merge elements into. Put this piece of code after you call your merge function from inside your mergeSort, it should give you some idea of what's wrong.


mResult = merge(gameRooms, startEl, middleElement, middleElement + 1, endEl, sortType);

cout<< "mResult(";
for( int i = 0; i < mResult.size(); ++i)
cout<< mResult.ID <<",";
cout<<")"<<endl;

Share this post


Link to post
Share on other sites
Thanks guys!

Problem was basically just a whole load of <= rather than < than. I will take your advice and use iterators.

I looked up std::sort, but I prefer writing the code myself, I can learn a lot more! Thanks anyway.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!