Find if elements of one array are present in the other and return a boolean array

[Shalini]

Hi ,
Is the code below efficient??

bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
charQuickSort(a2, 0, (lengtha2-1));
bool *tag=(bool*)calloc(lengtha1,sizeof(bool));

int i,j;
for(j = 0; j < lengtha1; j++){
for(i = 0; i < lengtha2;i++){
if(strcmp(a1[j],a2[i])==0){
tag[j]=true;
// printf("%d\n",tag[j]);
break;
}
if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
tag[j] = false;
// printf("%d\n",tag[j]);
break;
}
}
}

return(tag);
}
void charQuickSort(char **vals, int l, int r)
{
int i,j,m;
char **v=(char **)calloc(1,sizeof(char *));
char **t=(char **)calloc(1,sizeof(char *));

if(r > l)
{
m = (r+l)/2;
if(strcmp(vals[m] ,vals[r])<0)
{
if(strcmp(vals[l] ,vals[m])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
}
else if (strcmp(vals[l] ,vals[r])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);
}
}
else
{
if(strcmp(vals[l] ,vals[m])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
}
else if (strcmp(vals[l], vals[r])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);

}
}
v[0]=vals[r];
// strcpy(v,vals[r]);
i = l-1;
j = r;
do {

for(i++; strcmp(vals[i], v[0])<0 && i <= r; i++) {
// printf("%d ",i);
}
/*for(i++; strcmp(vals[i], v)<0 && i <= r; i++) {
//printf("%d ",i);
}*/

for(j--; strcmp(vals[j],v[0])>0 && j > l; j--);
// for(j--; strcmp(vals[j],v)>0 && j > l; j--);
t[0]=vals[i];
// strcpy(t,vals[i]);
vals[i] = vals[j];
vals[j] = t[0];
//vals[j] = strdup(t);

}
while( j > i);
vals[j] = vals[i];
vals[i] = vals[r];
vals[r] = t[0];
//vals[r] = strdup(t);
charQuickSort(vals, l, i-1);
charQuickSort(vals,i+1,r);
}

}

[Brian Genisio]

Shalini wrote:

Hi ,
Is the code below efficient??

bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
charQuickSort(a2, 0, (lengtha2-1));
bool *tag=(bool*)calloc(lengtha1,sizeof(bool));

int i,j;
for(j = 0; j < lengtha1; j++){
for(i = 0; i < lengtha2;i++){
if(strcmp(a1[j],a2[i])==0){
tag[j]=true;
// printf("%d\n",tag[j]);
break;
}
if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
tag[j] = false;
// printf("%d\n",tag[j]);
break;
}
}
}

return(tag);
}
void charQuickSort(char **vals, int l, int r)
{
int i,j,m;
char **v=(char **)calloc(1,sizeof(char *));
char **t=(char **)calloc(1,sizeof(char *));

if(r > l)
{
m = (r+l)/2;
if(strcmp(vals[m] ,vals[r])<0)
{
if(strcmp(vals[l] ,vals[m])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
}
else if (strcmp(vals[l] ,vals[r])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);
}
}
else
{
if(strcmp(vals[l] ,vals[m])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
}
else if (strcmp(vals[l], vals[r])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);

}
}
v[0]=vals[r];
// strcpy(v,vals[r]);
i = l-1;
j = r;
do {

for(i++; strcmp(vals[i], v[0])<0 && i <= r; i++) {
// printf("%d ",i);
}
/*for(i++; strcmp(vals[i], v)<0 && i <= r; i++) {
//printf("%d ",i);
}*/

for(j--; strcmp(vals[j],v[0])>0 && j > l; j--);
// for(j--; strcmp(vals[j],v)>0 && j > l; j--);
t[0]=vals[i];
// strcpy(t,vals[i]);
vals[i] = vals[j];
vals[j] = t[0];
//vals[j] = strdup(t);

}
while( j > i);
vals[j] = vals[i];
vals[i] = vals[r];
vals[r] = t[0];
//vals[r] = strdup(t);
charQuickSort(vals, l, i-1);
charQuickSort(vals,i+1,r);
}

}

Here is pseudocode for a very similar problem I needed to solve... I
solved it in O(nln), where your solution is O(n^2).

Problem: Given Arrays A1 and A2, find if there exist any in common
Solution:

1. Sort A1 with an O(nln) search. *hint... QuickSort is O(n^2) in worst
case, so it is not really the best, if you have a lot of numbers.... You
can do better, usually

2. For every item in A2 (O(n)), do a binary search for the item in A1
(O(ln), since it is sorted).

Each step is O(nln), which gives an O(nln) solution.

That is the fastest that I know how to solve the problem.
Brian

[Brian Genisio]

Brian Genisio wrote:

Shalini wrote:

Hi ,
Is the code below efficient??

bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
charQuickSort(a2, 0, (lengtha2-1));
bool *tag=(bool*)calloc(lengtha1,sizeof(bool));

int i,j;
for(j = 0; j < lengtha1; j++){
for(i = 0; i < lengtha2;i++){
if(strcmp(a1[j],a2[i])==0){
tag[j]=true;
// printf("%d\n",tag[j]);
break;
}
if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
tag[j] = false;
// printf("%d\n",tag[j]);
break;
}
}
}

return(tag);
}
void charQuickSort(char **vals, int l, int r)
{
int i,j,m;
char **v=(char **)calloc(1,sizeof(char *));
char **t=(char **)calloc(1,sizeof(char *));

if(r > l) {
m = (r+l)/2;
if(strcmp(vals[m] ,vals[r])<0)
{
if(strcmp(vals[l] ,vals[m])<0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
} else if (strcmp(vals[l]
,vals[r])<0) {
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);
}
} else
{
if(strcmp(vals[l] ,vals[m])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[m];
vals[m] = t[0];
//vals[m] = strdup(t);
} else if (strcmp(vals[l],
vals[r])>0)
{
t[0]=vals[r];
//strcpy(t,vals[r]);
vals[r] = vals[l];
vals[l] = t[0];
//vals[l] = strdup(t);

}
}
v[0]=vals[r];
// strcpy(v,vals[r]);
i = l-1;
j = r;
do {

for(i++; strcmp(vals[i], v[0])<0 && i <= r; i++) {
// printf("%d ",i);
}
/*for(i++; strcmp(vals[i], v)<0 && i <= r; i++) {
//printf("%d ",i);
}*/

for(j--; strcmp(vals[j],v[0])>0 && j > l; j--);
// for(j--; strcmp(vals[j],v)>0 && j > l; j--);
t[0]=vals[i];
// strcpy(t,vals[i]);
vals[i] = vals[j];
vals[j] = t[0];
//vals[j] = strdup(t);

} while( j > i);
vals[j] = vals[i];
vals[i] = vals[r];
vals[r] = t[0];
//vals[r] = strdup(t);
charQuickSort(vals, l, i-1);
charQuickSort(vals,i+1,r);
}
}

Here is pseudocode for a very similar problem I needed to solve... I
solved it in O(nln), where your solution is O(n^2).

Problem: Given Arrays A1 and A2, find if there exist any in common
Solution:

1. Sort A1 with an O(nln) search. *hint... QuickSort is O(n^2) in worst
case, so it is not really the best, if you have a lot of numbers.... You
can do better, usually

2. For every item in A2 (O(n)), do a binary search for the item in A1
(O(ln), since it is sorted).

Each step is O(nln), which gives an O(nln) solution.

That is the fastest that I know how to solve the problem.
Brian

After looking again, I did not give you a solution for the problem you
put out... sorry.

To clarify... quicksort cannot guarantee efficiency, so I would use
something else.... possibly a randomized quicksort, which is better for
the average time, but is still worst case O(n^2)

For your problem, I have a better solution (for speed efficiency)...

Sort BOTH arrays using an O(nln) sort.
Move pointers in both arrays, since they are both sorted... Using
integers, you can see, you can compare both in a _single scan. The same
is true for string compares.

1 3 4 6 7 10
1 2 5 6 7 9 10

This solution will solve your problem in O(nln), which beats your
current solution of O(n^2)

Brian