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_FAILURE);
}

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

}

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

[pete]

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.

/* BEGIN new.c output */

original array:
100 20 -45 -345 -2 120 64 99 20 15 0 1 25

left array:
-345 -45 -2 0 1 15 20 20 25

right array:
64 99 100 120

/* END new.c output */

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>

#define RIGHT 50

int compar(const void *, const void *);

int main(void)
{
size_t count;
int array[] = {100,20,-45,-345,-2,120,64,99,20,15,0,1,25};
int *right = array;

puts("/* BEGIN new.c output */\n");
puts("original array:");
for (count = 0; count != sizeof array / sizeof *array; ++count) {
printf("%d ", array[count]);
}
putchar('\n');
qsort(array, sizeof array / sizeof *array, sizeof *array, compar);
while (RIGHT *right
&& right != array + sizeof array / sizeof *array)
{
++right;
}
puts("\nleft array:");
for (count = 0; count != right - array + 0u; ++count) {
printf("%d ", array[count]);
}
puts("\n\nright array:");
for (count = 0;
count != sizeof array / sizeof *array - (right - array); ++count)
{
printf("%d ", right[count]);
}
puts("\n\n/* END new.c output */");
return 0;
}

int compar (const void *a, const void *b)
{
const int *pa = a;
const int *pb = b;

return *pb *pa ? -1 : *pb != *pa;
}

/* END new.c */
--
pete

[Richard Heathfield]

Keith Thompson said:

pereges <Br*****@gmail.comwrites:

<snip>

> if(a[i] <= 50)
left_size++;
if(a[i] 50)
right_size++;

The second test is unnecessary.

s/is unnecessary/can be replaced by else/

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Keith Thompson]

Richard Heathfield <rj*@see.sig.invalidwrites:

Keith Thompson said:

>pereges <Br*****@gmail.comwrites:

<snip>

>> if(a[i] <= 50)
left_size++;
if(a[i] 50)
right_size++;

The second test is unnecessary.

s/is unnecessary/can be replaced by else/

<snip>

Right.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[MJ_India]

On May 25, 3:21*pm, pereges <[e-mail]:

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.

[pereges]

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.

[Ben Bacarisse]

MJ_India <ma************@gmail.comwrites:

On May 25, 3:21Â*pm, pereges <[e-mail]:

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

<snip>

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

Presumably you intended to write endIndex--.

3. left = array, right = array + endIndex

--
Ben.

[Ben Bacarisse]

Keith Thompson <ks***@mib.orgwrites:

Richard Heathfield <rj*@see.sig.invalidwrites:

>Keith Thompson said:

>>pereges <Br*****@gmail.comwrites:

<snip>

>>> if(a[i] <= 50)
left_size++;
if(a[i] 50)
right_size++;

The second test is unnecessary.

s/is unnecessary/can be replaced by else/

<snip>

Right.

I prefer your correction because the whole second test *is*
unnecessary. The OP needs to write 'size_of_array - left_size' in the
allocation but that is all. At first reading I thought that was what
you intended.

--
Ben.

[Willem]

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

[CBFalconer]

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

[Ben Bacarisse]

Willem <wi****@stack.nlwrites:

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**********************************@z24g2000prf. googlegroups.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 <[e-mail]:

... 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 <[e-mail]:

>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