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]

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]

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.programming
instead of here, because it isn't really language limited.

Either way, your response was once again rude for no apparent reason.

 

[didgerman]

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]

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.

 

[CBFalconer]

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.programming.

 

[Ben Pfaff]

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?

 

[Tom St Denis]

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]

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]

.... 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.

 

[Ben Pfaff]

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.

Somehow Spamassassin decided it was spam. Will send reply.

 

[CBFalconer]

Somehow Spamassassin decided it was spam. Will send reply.

It would have the same From and Reply to as this, if that triggers
things.

 

[osmium]

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...

It's very clear. And kind of clever, too.

 

[Barry Schwarz]

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:

If you attack the problem from the back end, it may be easier. A
merge would normally have two inputs and an output. If you consider
the last entry of A as input 1, the last used entry of B as input 2,
and the last entry of B as the output, you can safely move data from
the appropriate either input to output repeatedly until you have
finished with the first elements of both inputs.


<<Remove the del for email>>

 

[Sidney Cadot]

Tom St Denis wrote:

[...]

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].

Yeah!

You really are a mean, bad, and way-cool dude, talking like that.

Rrrespect,

Sidney

 

[Michael Scovetta]

Way to post the Microsoft interview question. Hope they don't use google!

 

[pete]

If you attack the problem from the back end, it may be easier. A
merge would normally have two inputs and an output. If you consider
the last entry of A as input 1, the last used entry of B as input 2,
and the last entry of B as the output, you can safely move data from
the appropriate either input to output repeatedly until you have
finished with the first elements of both inputs.

I think that's the solution that the author of the problem had in mind.

 

[Richard Heathfield]

Simon Bachmann wrote:

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.

I was about to complain that you would need to reserve storage for ia and
ib, but of course you can use na and nb, which you get for free. Very neat.

 

[pete]

Simon Bachmann wrote:

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.

I was about to complain that you would need to reserve
storage for ia and ib, but of course you can use na and nb,
which you get for free. Very neat.

You still need another object to keep track of
the last (empty) element of b.

If you copy a[0], then you're done.
If you copy b[0], then you can copy the rest of a[]
without comparisons between the rest of the elements.

 

[pete]

Simon Bachmann wrote:

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.

I was about to complain that you would need to reserve
storage for ia and ib, but of course you can use na and nb,
which you get for free. Very neat.

I very much prefer the "pointer to element, size_t"
sorting function interface, which I got from Dann Corbit,
over the interface where everything is int and pointers to int,
for two reasons: 1 pedagogy, 2 practicality.

From a sorting algorithm point of view,
the objects which are used for book keeping inside the function,
like your ia and ib above, are conceptually,
completely different from the array elements which are also integers.

From practical point of view,
the function can be written as a template.

You can change E_TYPE to any arithmetic type without
affecting the ouptut of merge.c
If you wanted to sort non arithmetic types,
then the GT() macro would also need to be rewritten,
but you have to write a new compar function everytime you
want use qsort in a new way, so it's no big deal.

/* BEGIN merge.c */

#include <stdio.h>

#define arrayA {4, 7, 10, 15, 17}
#define arrayB {2, 4, 14, 27, 'X', 'X', 'X', 'X', 'X'}
#define E_TYPE int
#define GT(A, B) (*(A) > *(B))
#define N(E) (sizeof (E) / sizeof *(E))

typedef E_TYPE e_type;

void Merge(e_type *, size_t, e_type *, size_t);

int main(void)
{
e_type a[] = arrayA;
e_type b[] = arrayB;
size_t element;

Merge(a, N(a), b, N(b));
for (element = 0; element != N(b); ++element) {
printf("%lu, ", (long unsigned)b[element]);
}
putchar('\n');
return 0;
}

void Merge(e_type *a, size_t na, e_type *b, size_t nb)
{
e_type *end;

end = b + nb--;
nb -= na--;
for (; {
if (GT(b + nb, a + na)) {
*--end = b[nb];
if (nb == 0) {
break;
} else {
--nb;
}
} else {
*--end = a[na];
if (na == 0) {
return;
} else {
--na;
}
}
}
do {
*--end = a[na];
} while (na-- != 0);
}

/* END merge.c */

I like pointers:
/*
void Merge(e_type *a, size_t na, e_type *b, size_t nb)
{
e_type *end, *B, *A;

end = b + nb;
A = a + na - 1;
B = b + nb - na - 1;
for (; {
if (GT(B, A)) {
*--end = *B;
if (B == b) {
break;
} else {
--B;
}
} else {
*--end = *A;
if (A == a) {
return;
} else {
--A;
}
}
}
*--end = *A;
while (A != a) {
*--end = *--A;
}
}
*/