Velocity Reviews > Longer array out of two shorter arrays

# Longer array out of two shorter arrays

Mik0b0
Guest
Posts: n/a

 01-13-2007
Hallo everybody,
my problem is: there are two single-dimension arrays, longer[M] and
shorter[N], every array is organized in ascending order. We need to
build a new array out of two. This is what I wrote:
#include<stdio.h>
#define M 8
#define N 5
main()
{
int big[M]={1,2,5,8,10,23,45,56};
int small[N]={3,7,11,12,100};
int new[M+N];
int i=0,k=0,l=0;

while(l<(N+M))
{
if(small[k]<big[i])
{
new[l]=small[k];
k++;
l++;
}
else
{
new[l]=big[i];
i++;
l++;
}
}

for(l=0;l<(M+N);l++)
printf("%d ",new[l]);
printf("\n");
}

The output is:

[Mike@localhost drills]\$ ./153
1 2 3 5 7 8 10 11 12 23 45 56 8

Why is the last number wrong?

Ian Collins
Guest
Posts: n/a

 01-13-2007
Mik0b0 wrote:
> Hallo everybody,
> my problem is: there are two single-dimension arrays, longer[M] and
> shorter[N], every array is organized in ascending order. We need to
> build a new array out of two. This is what I wrote:
> #include<stdio.h>
> #define M 8
> #define N 5
> main()

int main(void)

<snip code>
>
> The output is:
>
> [Mike@localhost drills]\$ ./153
> 1 2 3 5 7 8 10 11 12 23 45 56 8
>

With which compiler? I see

1 2 3 5 7 8 10 11 12 23 45 56 100

--
Ian Collins.

Richard Heathfield
Guest
Posts: n/a

 01-13-2007
Mik0b0 said:

> Hallo everybody,
> my problem is: there are two single-dimension arrays, longer[M] and
> shorter[N], every array is organized in ascending order. We need to
> build a new array out of two. This is what I wrote:
> #include<stdio.h>
> #define M 8
> #define N 5
> main()
> {
> int big[M]={1,2,5,8,10,23,45,56};
> int small[N]={3,7,11,12,100};
> int new[M+N];
> int i=0,k=0,l=0;
>
> while(l<(N+M))
> {
> if(small[k]<big[i])

You don't check to ensure that k < N or that i < M. Once k == N, you need to
stop loading from 'small' and copy the rest of 'big', unless i == M. Once i
== M, you need to stop loading from 'big', and copy the rest of 'small',
unless k == N.

Fix that, and I reckon your problem will vanish.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

Ian Collins
Guest
Posts: n/a

 01-13-2007
Richard Heathfield wrote:
> Mik0b0 said:
>
>
>>Hallo everybody,
>>my problem is: there are two single-dimension arrays, longer[M] and
>>shorter[N], every array is organized in ascending order. We need to
>>build a new array out of two. This is what I wrote:
>>#include<stdio.h>
>>#define M 8
>>#define N 5
>>main()
>>{
>>int big[M]={1,2,5,8,10,23,45,56};
>>int small[N]={3,7,11,12,100};
>>int new[M+N];
>>int i=0,k=0,l=0;
>>
>>while(l<(N+M))
>>{
>>if(small[k]<big[i])

>
>
> You don't check to ensure that k < N or that i < M.

Good catch.

--
Ian Collins.

woodstok
Guest
Posts: n/a

 01-13-2007

On Jan 12, 5:14 pm, "Mik0b0" <(E-Mail Removed)> wrote:
> Hallo everybody,
> my problem is: there are two single-dimension arrays, longer[M] and
> shorter[N], every array is organized in ascending order. We need to
> build a new array out of two. This is what I wrote:
> #include<stdio.h>
> #define M 8
> #define N 5
> main()

main returns an int. Always.

> {
> int big[M]={1,2,5,8,10,23,45,56};
> int small[N]={3,7,11,12,100};
> int new[M+N];
> int i=0,k=0,l=0;
>
> while(l<(N+M))
> {
> if(small[k]<big[i])

what happens in the above line if k > N or i > M?

> {
> new[l]=small[k];
> k++;
> l++;
> }
> else
> {
> new[l]=big[i];
> i++;
> l++;
> }
> }
>
> for(l=0;l<(M+N);l++)
> printf("%d ",new[l]);
> printf("\n");
>

return 0;

> }The output is:
>
> [Mike@localhost drills]\$ ./153
> 1 2 3 5 7 8 10 11 12 23 45 56 8
>
> Why is the last number wrong?

Richard Heathfield
Guest
Posts: n/a

 01-13-2007
woodstok said:

>
>
> On Jan 12, 5:14 pm, "Mik0b0" <(E-Mail Removed)> wrote:
>> Hallo everybody,
>> my problem is: there are two single-dimension arrays, longer[M] and
>> shorter[N], every array is organized in ascending order. We need to
>> build a new array out of two. This is what I wrote:
>> #include<stdio.h>
>> #define M 8
>> #define N 5
>> main()

>
> main returns an int. Always.

Yes, and:

main()

defines main as returning int. Always. (Except in C99thud[1].)

>
>> {
>> int big[M]={1,2,5,8,10,23,45,56};
>> int small[N]={3,7,11,12,100};
>> int new[M+N];
>> int i=0,k=0,l=0;
>>
>> while(l<(N+M))
>> {
>> if(small[k]<big[i])

>
> what happens in the above line if k > N or i > M?

ITYM >= in each case.

[1] Q: What goes 99 thud?
A: A centipede with a wooden leg.

Q: What else goes 99 thud?
A: The latest C Standard going down like a lead balloon.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

Mik0b0
Guest
Posts: n/a

 01-13-2007

Ian Collins wrote:
> Mik0b0 wrote:
> > Hallo everybody,
> > my problem is: there are two single-dimension arrays, longer[M] and
> > shorter[N], every array is organized in ascending order. We need to
> > build a new array out of two. This is what I wrote:
> > #include<stdio.h>
> > #define M 8
> > #define N 5
> > main()

> int main(void)
>
> <snip code>
> >
> > The output is:
> >
> > [Mike@localhost drills]\$ ./153
> > 1 2 3 5 7 8 10 11 12 23 45 56 8
> >

> With which compiler? I see
>
> 1 2 3 5 7 8 10 11 12 23 45 56 100
>
> --
> Ian Collins.

I use gcc.

woodstok
Guest
Posts: n/a

 01-13-2007

On Jan 12, 5:38 pm, Richard Heathfield <(E-Mail Removed)> wrote:
> woodstok said:
>
>
>
> > On Jan 12, 5:14 pm, "Mik0b0" <(E-Mail Removed)> wrote:
> >> main()

>
> > main returns an int. Always.

> Yes, and:
>
> main()
>
> defines main as returning int. Always. (Except in C99thud[1].)
>

So.. not always then.

>
> >> {
> >> int big[M]={1,2,5,8,10,23,45,56};
> >> int small[N]={3,7,11,12,100};
> >> int new[M+N];
> >> int i=0,k=0,l=0;

>
> >> while(l<(N+M))
> >> {
> >> if(small[k]<big[i])

>
> > what happens in the above line if k > N or i > M?

> ITYM >= in each case.
>

Yes I did. Thanks for catching that.

CBFalconer
Guest
Posts: n/a

 01-13-2007
Mik0b0 wrote:
>
> my problem is: there are two single-dimension arrays, longer[M] and
> shorter[N], every array is organized in ascending order. We need to
> build a new array out of two. This is what I wrote:

You are allowed to use spaces. There are no prizes for obfuscation
by eliding them, and they are no longer on allocation. You are
also allowed to use reasonable indentation.
>
> #include<stdio.h>
> #define M 8
> #define N 5
> main()

int main(void)

> {
> int big[M]={1,2,5,8,10,23,45,56};
> int small[N]={3,7,11,12,100};
> int new[M+N];
> int i=0,k=0,l=0;
>
> while(l<(N+M))

while ((i < N) && (k < M))
> {
> if(small[k]<big[i])
> {
> new[l]=small[k];
> k++;
> l++;
> }
> else
> {
> new[l]=big[i];
> i++;
> l++;
> }
> }
>

while (i < M) new[l++] = big[i++];
while (k < N) new[l++] = small[k++];

> for(l=0;l<(M+N);l++)
> printf("%d ",new[l]);
> printf("\n");

return 0;
> }
>
> The output is:
>
> [Mike@localhost drills]\$ ./153
> 1 2 3 5 7 8 10 11 12 23 45 56 8
>
> Why is the last number wrong?

--
"I was born lazy. I am no lazier now than I was forty years
ago, but that is because I reached the limit forty years ago.
You can't go beyond possibility." -- Mark Twain

CBFalconer
Guest
Posts: n/a

 01-13-2007
CBFalconer wrote:
> Mik0b0 wrote:
>
>> my problem is: there are two single-dimension arrays, longer[M] and
>> shorter[N], every array is organized in ascending order. We need to
>> build a new array out of two. This is what I wrote:

>
> You are allowed to use spaces. There are no prizes for obfuscation
> by eliding them, and they are no longer on allocation. You are
> also allowed to use reasonable indentation.
>>
>> #include<stdio.h>
>> #define M 8
>> #define N 5
>> main()

>
> int main(void)
>
>> {
>> int big[M]={1,2,5,8,10,23,45,56};
>> int small[N]={3,7,11,12,100};
>> int new[M+N];
>> int i=0,k=0,l=0;
>>

.... snip code ...

As an example, here is how I would have coded it. Note that now
things are defined in one place, and the heart can be freely
modified. The key is the use of sizeof to extract what you defined
as M and N, and the slaving of the *ix names to the names of the
variables they index. The #define for sz is a dog-standard way of
extracting the size of an array. It is a compile time constant, so
it does not complicate the emitted code. size_t is an unsigned
type, which can always measure the size of an array in bytes, and
is the type returned by sizeof and thus by sz. Think about why at
most only one of the final while loops will be executed.

You might want to look up the use of loop-invariants to deduce the
validity of code.

#include <stdio.h>
int main(void)
{
int big[] = {1, 2, 5, 8, 10, 23, 45, 56};
int small[] = {3, 7, 11, 12, 100};

#define sz(a) (sizeof a / sizeof a[0])

int new[sz(big) + sz(small)];
size_t bigix, smallix, newix;

bigix = smallix = newix = 0;
while ((bigix < sz(big)) && (smallix < sz(small)))
if (small[smallix] < big[bigix])
new[newix++] = small[smallix++];
else
new[newix++] = big[bigix++];

while (bigix < sz(big))
new[newix++] = big[bigix++];
while (smallix < sz(small))
new[newix++] = small[smallix++];

for (newix = 0; newix < (sz(big) + sz(small)); newix++)
printf("%d ", new[newix]);
putchar('\n');

return 0;
} /* main */

/* note that the index names are now tied to the arrays
that they index, and that the various sizes are tied
to the arrays that they describe. You should now be
able to modify the array initializations and have the
remainder of the code automatically adjust. */

--
"I was born lazy. I am no lazier now than I was forty years
ago, but that is because I reached the limit forty years ago.
You can't go beyond possibility." -- Mark Twain