Jump to content
  • Advertisement
Sign in to follow this  
y2jsave

merging 2 parts of a array !!

This topic is 2802 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 folks,

given a array .
its first half is sorted .
its second half is sorted .

now we have to sort the complete array . in place . we cant use a new array to store the result ..

thanjk in advance
y2jsave

Share this post


Link to post
Share on other sites
Advertisement
In particular, you should take a look at the merge sort algorithm.

http://en.wikipedia.org/wiki/Merge_sort

Share this post


Link to post
Share on other sites
but the problem is that we cant create a new array to save the final sorted array ..

so i dont know how to apply merge sort ..

however , i feel that a modified version of merge sort may be used here .. which i tried to think but could not

Share this post


Link to post
Share on other sites
nah, just compare the first element and the element just after the half point.
if the first element is bigger, do an in-place swap:

6789 1234
1789 6234
1289 6734
1239 6784
1234 6789
done!

OR

1234 6789
done!

Share this post


Link to post
Share on other sites
Then you would need to do an in-place merge, something like this perhaps:
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
or this
http://www.cs.ubc.ca/~harrison/Java/MergeSortAlgorithm.java.html

Share this post


Link to post
Share on other sites
Off the top of my head:


for (int f = 0; f < first.size(); ++ f)
{

for (int s = second.size() - 1; s >= 0; -- s)
{

if (second[s] < first[f])
{

int temp = first[f];
first[f] = second[s];
second[s] = temp;

}

}

}





Edit: Even better!

Also, if your halves aren't pre-sorted, you can sort them after doing the above. As an alternative to using the temp variable you can use the XOR method or swapping in place.

Edit2: (vvvvvv) Bah, I misread the question as needing to sort two separate pre-sorted arrays in place as if they were one. Obviously this is O(n^2) and doesn't apply if it's one array. Oh well, I had fun thinking about it =P

[Edited by - 1863 on November 14, 2010 7:11:40 PM]

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!