Velocity Reviews > how can i do this in o(n)

# how can i do this in o(n)

kitts
Guest
Posts: n/a

 09-14-2005
A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

Walter Roberson
Guest
Posts: n/a

 09-14-2005
In article < om>,
kitts <> wrote:
>A given array of size 2n with n elements in sorted order. Another array
>with size n & n elements in it in sorted order. Merge the two arrays &
>final array should be in sorted order without using extra memory

That sounds like an assignment question.

How does one know where the n elements are in the array of size 2n ?
The question as stated does -not- indicate that the n elements
are at the beginning of the array, nor that the n elements are
evenly distributed -- only that the elements are in order.

--
"Never install telephone wiring during a lightning storm." -- Linksys

Martin Ambuhl
Guest
Posts: n/a

 09-14-2005
kitts wrote:
> A given array of size 2n with n elements in sorted order. Another array
> with size n & n elements in it in sorted order. Merge the two arrays &
> final array should be in sorted order without using extra memory

Not today. Post your instructor's name and email address, and I'm sure

Richard Heathfield
Guest
Posts: n/a

 09-14-2005
(Subject line: "how can i do this in o(n)")

kitts said:

> A given array of size 2n with n elements in sorted order. Another array
> with size n & n elements in it in sorted order. Merge the two arrays &
> final array should be in sorted order without using extra memory

Consider writing a C function to do it. Post your best-effort code if you
get stuck.Here's an algorithm hint, using playing cards (E means "empty
slot"):

A 5 6 9 E E E E

2 7 8 K

You can compare the last card in each deck, and move the highest value card
out of those two to the last empty slot in the upper deck. Then compare
whichever card "lost" the previous comparison to the last card in the other
deck that has not yet been shoved into all that lovely space at the back.

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

Ben Pfaff
Guest
Posts: n/a

 09-14-2005
"kitts" <> writes:

[ Subject: how can i do this in o(n) ]
> A given array of size 2n with n elements in sorted order. Another array
> with size n & n elements in it in sorted order. Merge the two arrays &
> final array should be in sorted order without using extra memory

I don't think this problem is solvable in o(n) time.
I think it should be solvable in O(n).
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

Christian Bau
Guest
Posts: n/a

 09-14-2005
In article < om>,
"kitts" <> wrote:

> A given array of size 2n with n elements in sorted order. Another array
> with size n & n elements in it in sorted order. Merge the two arrays &
> final array should be in sorted order without using extra memory

Not possible in o (n).
Trivial in O (n).

August Karlstrom
Guest
Posts: n/a

 09-15-2005
kitts wrote:
> A given array of size 2n with n elements in sorted order. Another array
> with size n & n elements in it in sorted order.

An array of n elements of which n elements are sorted... sounds like a
(fully) sorted array!?

August

Alan Balmer
Guest
Posts: n/a

 09-15-2005
On Thu, 15 Sep 2005 00:20:23 GMT, August Karlstrom
<> wrote:

>kitts wrote:
>> A given array of size 2n with n elements in sorted order. Another array
>> with size n & n elements in it in sorted order.

>
>An array of n elements of which n elements are sorted... sounds like a
>(fully) sorted array!?
>

Yes. There is some question about the composition of the other array,
however.
--
Al Balmer
Balmer Consulting

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Edward A. Falk C Programming 1 04-04-2013 08:07 PM Casey Hawthorne Java 1 03-18-2009 12:56 AM Martin Computer Support 16 02-24-2009 07:35 PM 02befree Computer Support 0 12-24-2007 09:10 PM jameshanley39@yahoo.co.uk Computer Information 2 09-19-2007 02:53 AM