help with sorting

[ruel loehr]

Hey guys,

I am looking for some insight:
Given two sorted arrays of integers A and B, where array B has enough
extra room in it to hold the contents of both A and B. Merge array A
and B together such that the result is the sorted combination of the
two (do not remove duplicates) and the result resides in the B array.
I cannot perform any memory allocations to solve the problem.
Performance considerations should be taken into account in your
solution (so brute force method is not an option). Here is some
example data to help explain:

Array A: 4 7 10 15 17
Array B: 2 4 14 27 X X X X X

Where the X'es are unused slots in array B. The solution would end up
with B looking like this:

Array B: 2 4 4 7 10 14 15 17 27
Using the following function prototype:

void Merge (int *a, int na, int *b, int nb)

Where a and b point to the two arrays, na and nb are the number of
elements in each array. For array b, nb is the number of used
elements, not the size of the array. Assume array b is large enough to
hold the contents of a and b. Using the above example data na would be
5 and nb would be 4.

Also please specify the order of complexity for the algorithm you
chose to solve the problem.

My first thoughts are merge sort of course, although it requires your
to perform additional memory allocation. This leads to me an in
place merge sort.

What do you guys thinks? Any suggestions? Code isn't so important (i
can write that) but I am looking for help with the algorithm.
Thanks!

[Tom St Denis]

"ruel loehr" <ru*******@hotm ail.com> wrote in message
news:50******** *************** ***@posting.goo gle.com...

Hey guys,

I am looking for some insight:

This is called merge sorting.

How about instead of asking someone here todo your homework you attend
class, read the suggested material, google and trial-and-error?

Tom

[Randy Howard]

In article <bD************ ******@news04.b loor.is.net.cab le.rogers.com>,
to********@iahu .ca says...

"ruel loehr" <ru*******@hotm ail.com> wrote in message
news:50******** *************** ***@posting.goo gle.com...

Hey guys,

I am looking for some insight:
This is called merge sorting.

Which was mentioned in the original. You snipped it, for whatever
reason.
How about instead of asking someone here todo your homework you attend
class, read the suggested material, google and trial-and-error?

He was asking for opinions about how to implement, and also said that
he was not looking for the code, but merely suggestions about how to
implement it. You snipped that again, for suspect reasons.

That being said, this should probably be asked in comp.programmin g
instead of here, because it isn't really language limited.

Either way, your response was once again rude for no apparent reason.
--
Randy Howard
2reply remove FOOBAR

[didgerman]

"ruel loehr" <ru*******@hotm ail.com> wrote in message
news:50******** *************** ***@posting.goo gle.com...

Hey guys,

I am looking for some insight:
Given two sorted arrays of integers A and B, where array B has enough extra room in it to hold the contents of both A and B. Merge array A
and B together such that the result is the sorted combination of the
two (do not remove duplicates) and the result resides in the B array. I cannot perform any memory allocations to solve the problem.
Performance considerations should be taken into account in your
solution (so brute force method is not an option). Here is some
example data to help explain:

Array A: 4 7 10 15 17
Array B: 2 4 14 27 X X X X X

Where the X'es are unused slots in array B. The solution would end up with B looking like this:

Array B: 2 4 4 7 10 14 15 17 27
Using the following function prototype:

void Merge (int *a, int na, int *b, int nb)

Where a and b point to the two arrays, na and nb are the number of
elements in each array. For array b, nb is the number of used
elements, not the size of the array. Assume array b is large enough to hold the contents of a and b. Using the above example data na would be 5 and nb would be 4.

Also please specify the order of complexity for the algorithm you
chose to solve the problem.

My first thoughts are merge sort of course, although it requires your to perform additional memory allocation. This leads to me an in
place merge sort.

What do you guys thinks? Any suggestions? Code isn't so important (i can write that) but I am looking for help with the algorithm.
Thanks!

Try this:
strcat(arrayB, arrayA);

That should work.
As our grumpy friend says, do a search on google for the strcat
function and the headers it needs.
Be aware that there is no white space etween the arrays once this has
been done.
I'm lazy so I just added an array of one whitespace first, then added
the second array.
This function returns the first array's name as the new combined
array.
You can right code to check it will all fit before the cat' takes
place.
hth

[Randy Howard]

In article <50************ **************@ posting.google. com>,
ru*******@hotma il.com says...

Given two sorted arrays of integers A and B, where array B has enough
extra room in it to hold the contents of both A and B. Merge array A
and B together such that the result is the sorted combination of the
two (do not remove duplicates) and the result resides in the B array.
I cannot perform any memory allocations to solve the problem.
Performance considerations should be taken into account in your
solution (so brute force method is not an option).

Well, depending on what the definition of "brute force" is in your
class, I think the simplest solution, given there will always be
sufficient room in array B to hold all of A, is to simply copy the
contents of array A into the unused slots in B. The use whatever
sort algorithm defies the rules against "brute force" and does not
require memory allocation while preserving duplicates. Bubble,
quicksort, shellsort, etc. should all be suitable once you get
the data into B, with no memory allocation required.

That's probably not what the instructor is looking for, but it seems
like an awfully straightforward method, and it could be done using
the Merge() prototype provided.
--
Randy Howard
2reply remove FOOBAR

[CBFalconer]

ruel loehr wrote:

I am looking for some insight:

Given two sorted arrays of integers A and B, where array B has enough
extra room in it to hold the contents of both A and B. Merge array A
and B together such that the result is the sorted combination of the
two (do not remove duplicates) and the result resides in the B array.
I cannot perform any memory allocations to solve the problem.
Performance considerations should be taken into account in your
solution (so brute force method is not an option). Here is some
example data to help explain:

Array A: 4 7 10 15 17
Array B: 2 4 14 27 X X X X X

Where the X'es are unused slots in array B. The solution would end up
with B looking like this:

Array B: 2 4 4 7 10 14 15 17 27
Using the following function prototype:

void Merge (int *a, int na, int *b, int nb)

Where a and b point to the two arrays, na and nb are the number of
elements in each array. For array b, nb is the number of used
elements, not the size of the array. Assume array b is large enough to
hold the contents of a and b. Using the above example data na would be
5 and nb would be 4.

Also please specify the order of complexity for the algorithm you
chose to solve the problem.

My first thoughts are merge sort of course, although it requires your
to perform additional memory allocation. This leads to me an in
place merge sort.

What do you guys thinks? Any suggestions? Code isn't so important (i
can write that) but I am looking for help with the algorithm.

You are in the wrong place for the algorithm. I can think of one
that is O(n) and needs no additional allocation, provided we can
tell XX from an entry. Try comp.programmin g.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Ben Pfaff]

"didgerman" <aw******@hotma il.com> writes:

"ruel loehr" <ru*******@hotm ail.com> wrote in message
news:50******** *************** ***@posting.goo gle.com...

Given two sorted arrays of integers A and B, where array B has

enough

Try this:
strcat(arrayB, arrayA);

That should work.

Did you fail to read the OP's article or do you just like giving
stupid and incorrect advice?
--
"The way I see it, an intelligent person who disagrees with me is
probably the most important person I'll interact with on any given
day."
--Billy Chambless

[Tom St Denis]

"Ben Pfaff" <bl*@cs.stanfor d.edu> wrote in message
news:87******** ****@pfaff.stan ford.edu...

"didgerman" <aw******@hotma il.com> writes:

"ruel loehr" <ru*******@hotm ail.com> wrote in message
news:50******** *************** ***@posting.goo gle.com...

Given two sorted arrays of integers A and B, where array B has

enough

Try this:
strcat(arrayB, arrayA);

That should work.

Did you fail to read the OP's article or do you just like giving
stupid and incorrect advice?

My guess was that was intentional [e.g. give horribly bad advice so the
stupid fucking idiot won't fucking come back here to cheat on his/her/it's
assignment].

That's just my understanding. I could be wrong.

Tom

[Simon Bachmann]

ruel loehr wrote:

Hey guys,

I am looking for some insight:

Given two sorted arrays of integers A and B, where array B has enough
extra room in it to hold the contents of both A and B. Merge array A
and B together such that the result is the sorted combination of the
two (do not remove duplicates) and the result resides in the B array.
I cannot perform any memory allocations to solve the problem.
Performance considerations should be taken into account in your
solution (so brute force method is not an option). Here is some
example data to help explain:

Array A: 4 7 10 15 17
Array B: 2 4 14 27 X X X X X

Where the X'es are unused slots in array B. The solution would end up
with B looking like this:

Array B: 2 4 4 7 10 14 15 17 27
Using the following function prototype:

void Merge (int *a, int na, int *b, int nb)

Where a and b point to the two arrays, na and nb are the number of
elements in each array. For array b, nb is the number of used
elements, not the size of the array. Assume array b is large enough to
hold the contents of a and b. Using the above example data na would be
5 and nb would be 4.

Also please specify the order of complexity for the algorithm you
chose to solve the problem.

My first thoughts are merge sort of course, although it requires your
to perform additional memory allocation. This leads to me an in
place merge sort.

What do you guys thinks? Any suggestions? Code isn't so important (i
can write that) but I am looking for help with the algorithm.

Thanks!

I would do something like this:

-you need two counters(ia ib): one for a, one for b. their initial value
is na respecively nb
-use this counters to compare the respective elements of the two arrays
-copy the greather to the last (empty) element of b
-decrease the counter ia OR ib (ia if a[ia] > b[ib], ib otherwise)
-go on "filling up" b from the last element towards the first, comparing
a[ia] b[ib]

This way you need no additional memory allocation, and work will be done
with exactly na+nb passages.

Hope you understand my description. it isn't that clear...

[CBFalconer]

Ben Pfaff wrote:

.... snip ...
Did you fail to read the OP's article or do you just like giving
stupid and incorrect advice?

I sent you an e-mail a few days ago, and got no reply, yet
something in the newsgroups got an immediate response. Did you
receive anything from me? I have some things to bring up.

BTW give thanks that he is not Trollsdale, St Denis, or Nilges.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!