Quick merge sort question
Author
Hi when using a merge sort with two sorted(ascending) arrays, does it work like this:
if (array1[0] < array2[0])
result[0] = array1[0]
result[1] = array2[0]
else
result[0] = array2[0]
result[1] = array1[0]
endif
and so on while iterating the lists, but also what happens when the two arrays are of different sizes eg:
1 4 6 9
1 7 11
a brief description would be fine thanks!
Sort of... [grin]. See merge sort.
It's more like
if (array1[0] < array2[0])
result[0] = array1[0]
else
result[0] = array2[0]
endif
The thing is that there's no guarantee that
array2[0] < array1[1]
so just deal with adding one result at a time.
With your sample set
1 4 6 9
1 7 11
it's clear that two items from the top list would be added consequetively. Switching back and forth between the two would leave the result unsorted
1 1 4 7 6 11 9 rather than 1 1 4 6 7 9 11
The algorithm should acount for the possibility of different sized sub arrays.
It's more like
if (array1[0] < array2[0])
result[0] = array1[0]
else
result[0] = array2[0]
endif
The thing is that there's no guarantee that
array2[0] < array1[1]
so just deal with adding one result at a time.
With your sample set
1 4 6 9
1 7 11
it's clear that two items from the top list would be added consequetively. Switching back and forth between the two would leave the result unsorted
1 1 4 7 6 11 9 rather than 1 1 4 6 7 9 11
The algorithm should acount for the possibility of different sized sub arrays.
Author
Thanks
This has to be the most confusing sort of them all!, unfortunently i can see why it is useful
I ended up copying the sort on wiki :), i'll learn it better later, sleep time!
This has to be the most confusing sort of them all!, unfortunently i can see why it is useful
I ended up copying the sort on wiki :), i'll learn it better later, sleep time!
vector < int > merge( vector < int > v1, vector < int > v2){ vector < int > result; int ind1 = 0; int ind2 = 0; if(!v1.size()) { return v2; } if(!v2.size()) { return v1; } while((ind1 < v1.size()) && (ind2 < v2.size())) { if(v1[ind1] <= v2[ind2]) { result.push_back(v1[ind1]); ind1++; } else { result.push_back(v2[ind2]); ind2++; } } while(ind1 < v1.size()) { result.push_back(v1[ind1]); ind1++; } while(ind2 < v2.size()) { result.push_back(v2[ind2]); ind2++; } return result; }Quote:Original post by johnnyBravoWhat makes you say that? I know a number of far more difficult to understand sorts. e.g Smoothsort.
This has to be the most confusing sort of them all!,
Quote:unfortunently i can see why it is usefulYes, very much so, although it has it's downsides also.
Quote:I ended up copying the sort on wiki :), i'll learn it better later, sleep time!Make sure you do, especially if this was for some coursework. It's really simple if you break it down into little steps. I suggest writing comments throughout the algorithm, as you work out what each bit does, then if you like, you could post it with comments later, to see if your understanding is correct.
Not difficult at all: just try it yourself.
Take a deck of cards and split it into two piles of unequal size, and sort each however you like. Then put them face down and turn up one card from each. By iteratively taking the top card from either (and choosing correctly - but it will be obvious how from just trying it) and putting them onto a new pile, you will end up with a totally sorted deck. Unevenness in size is no problem: if you *can't* take from one deck (because it has run out), then obviously you just take from the other.
Now try shuffling the deck and doing all the sorting this way, recursively. :)
Take a deck of cards and split it into two piles of unequal size, and sort each however you like. Then put them face down and turn up one card from each. By iteratively taking the top card from either (and choosing correctly - but it will be obvious how from just trying it) and putting them onto a new pile, you will end up with a totally sorted deck. Unevenness in size is no problem: if you *can't* take from one deck (because it has run out), then obviously you just take from the other.
Now try shuffling the deck and doing all the sorting this way, recursively. :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
