pereges wrote:
) I've an array :
)
) {100,20, -45 -345, -2 120, 64, 99, 20, 15, 0, 1, 25}
)
) I want to split it into two different arrays such that every number <=
) 50 goes into left array and every number > 50 goes into right array.
) I've done some coding but I feel this code is very inefficient:
)
<snip code>: first calculate sizes of arrays, allocate, and copy.
)
) I'm really not comfortable with running similar for loops two times.
) Is this bad programming ?

As others have pointed out, it is only slightly inefficient.

But it rather depends on the exact requirements of the function.
For example:
- Is it required that the function return two malloc()ed pointers ?
(That is, two pointers that can both be free()d ?)
- Is it required that the order of the items is retained ?
- How large are the lists in practise, and is it important that no
memory is wasted ?

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Well, I had given an example of a more general case where the array is
split using some random value. But what if I want to split the array
using the median of the array list in such way that all the elements
<= median go into a left array and all elements > median go into the
right array. It is necessary to create two different arrays in my
function and for that I need to know the max size for each array. To
find the median, you obviously need to sort it.

pereges wrote:
>
> To find the median, you obviously need to sort it.

Oh? That's news to me.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **

pereges wrote:
) Well, I had given an example of a more general case where the array is
) split using some random value. But what if I want to split the array
) using the median of the array list in such way that all the elements
)<= median go into a left array and all elements > median go into the
) right array. It is necessary to create two different arrays in my
) function and for that I need to know the max size for each array. To
) find the median, you obviously need to sort it.

- If you want to split on the median, then you know the size of the two
arrays beforehand.

- Finding the median can be done in O(N) time theoretically but that
has a lot of overhead.

- If you want to split on some given value and you have to have two
malloc()ed pointers that can be freed, you have no choice but to do
two passes.
However: If all you need are two pointers to memory with the resulting
two arrays, but it is not needed for the second array to be free()able,
then you can malloc() one array which will hold the two results, and
fill it from both ends, as suggested elsethread.
In other words: 'It is necessary to create two different arrays' is not
a good enough description of the requirements.

What is it actually that you are trying to do ? What is the function for ?


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem <willem@stack.nl> writes:

> pereges wrote:
> ) ... It is necessary to create two different arrays in my
> ) function and for that I need to know the max size for each array.
<snip>
> - If you want to split on some given value and you have to have two
> malloc()ed pointers that can be freed, you have no choice but to do
> two passes.

A bit extra: "and you want the arrays to be as small as possible". If
two independently free-able arrays are required, they could both be
allocated the same size as the original.

> What is it actually that you are trying to do ? What is the
> function for ?

Seconded.

--
Ben.

In article <b9b99c67-4515-486e-98c8-7bce77687781@z24g2000prf.googlegroups.com>,
pereges <Broli00@gmail.com> wrote:
>To find the median, you obviously need to sort it.

You can find the median using a quicksort-like algorithm in which you
only bother to "sort" the partition containing the median (e.g. if
you initially split 20 items into 8 and 12 you know it's in the 12).
This is O(N).

-- Richard
--
In the selection of the two characters immediately succeeding the numeral 9,
consideration shall be given to their replacement by the graphics 10 and 11 to
facilitate the adoption of the code in the sterling monetary area. (X3.4-1963)

On May 25, 5:03pm, pereges <Brol...@gmail.com> wrote:
> ... what if I want to split the array
> using the median of the array list ... To
> find the median, you obviously need to sort it.

There is an *expected-time* O(N) median algorithm
that will be just what you want. The overhead
work done by the median finder will be precisely
the array splitting you want to do anyway!
The algorithm is simply quicksort except that
you needn't actually do the subsorts.

Hope this s.
James Dow Allen