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 ?

[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.in validwrites:

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_Keit h) 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 <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.

[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.comwrite s:

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

>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.orgw rites:

Richard Heathfield <rj*@see.sig.in validwrites:

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