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!

[osmium]

Simon Bachmann writes:

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

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

[Ben Pfaff]

CBFalconer <cb********@yah oo.com> writes:

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.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[CBFalconer]

Ben Pfaff wrote:

CBFalconer <cb********@yah oo.com> writes:

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.

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

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

[Barry Schwarz]

On 17 Jan 2004 08:28:31 -0800, ru*******@hotma il.com (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:

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!

ru*******@hotma il.com (ruel loehr) wrote in message news:<50******* *************** ****@posting.go ogle.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!

[pete]

Barry Schwarz wrote:

On 17 Jan 2004 08:28:31 -0800, ru*******@hotma il.com (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:

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.

--
pete

[Richard Heathfield]

Simon Bachmann wrote:

<snip>

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.

--
Richard Heathfield : bi****@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[pete]

Richard Heathfield wrote:

Simon Bachmann wrote:

<snip>

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

[pete]

Richard Heathfield wrote:

Simon Bachmann wrote:

<snip>

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;
}
}
*/
--
pete