splitting an array.

[pereges]

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:

void split_array(int *a, int size_of_array)
{
/* a is the pointer to the array which is going to be partitioned */
int i, left_size =0, right_size = 0;

int *b, *c /* pointers to new arrays */

for(i =0; i< size_of_array; i++)
{
if(a[i] <= 50)
left_size++;
if(a[i] 50)
right_size++;
}

b = calloc(sizeof(* b) * left_size);
c = calloc(sizeof(* c) * right_size);

if( b == NULL || c == NULL)
{
fprintf(stderr, "memory allocation failure: %s %d %s", __FILE__,
__LINE__, __func__);
exit(EXIT_FAILU RE);
}

left_size = right_size = 0;

for(i =0; i< size_of_array; i++)
{
if(a[i] <= 50)
{
b[left_size] = a[i];
left_size++;
}
if(a[i] 50)
{
c[right_size] = a[i];
right_size++;
}
}

exit(EXIT_SUCCE SS);

}

I'm really not comfortable with running similar for loops two times.
Is this bad programming ?

[Ben Bacarisse]

Willem <wi****@stack.n lwrites:

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.

[Richard Tobin]

In article <b9************ *************** *******@z24g200 0prf.googlegrou ps.com>,
pereges <Br*****@gmail. comwrote:

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

[James Dow Allen]

On May 25, 5:03*pm, pereges <Brol...@gmail. comwrote:

... 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 helps.
James Dow Allen

[Bartc]

MJ_India wrote:

On May 25, 3:21 pm, pereges <Brol...@gmail. comwrote:

>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: . . .
I'm really not comfortable with running similar for loops two times.
Is this bad programming ?

1. Take startIndex = 0, endIndiex = sizeof(array) - 1;
2. Perform steps 2.1 and 2.2 in loop while startIndex < endIndex
2.1 if array[startIndex] <= 50, startIndex++
2.2 else exchange(array + startIndex, array + (endIndex++))
3. left = array, right = array + endIndex

Implementation is left to you. Moreover this is more an algorithm
question than a C question. I am afraid it was asked in wrong forum.

As specified it seemed the OP wanted two new arrays from the original data.

In this case, because the sizes are initially unknown, then it does become a
C question: how to allocate arrays without doing an extra pass through the
data. These little details are important in C, and once sorted the solution
is likely to be one of the fastest.

Otherwise the solution is trivial in some languages. Here's one I've just
tried:

data:=(100,20, -45, -345, -2, 120, 64, 99, 20, 15, 0, 1, 25)

a:=b:=()
forall x in data do
(x<50 | a | b) &:=x
end

println "Left =",a
println "Right =",b

And many will do it in one line I'm sure ("K" probably in a single
expression).

(I also ignored the new array requirement in my other post, but I'd also
missed the fact that everyone else also made use of sorting. Never mind..)

--
Bartc