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

Discussion in 'C++' started by Shalini, Jan 9, 2004.

  1. Shalini

    Shalini Guest

    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)==0){
    tag[j]=true;
    // printf("%d\n",tag[j]);
    break;
    }
    if(strcmp(a1[j],a2)<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, v[0])<0 && i <= r; i++) {
    // printf("%d ",i);
    }
    /*for(i++; strcmp(vals, 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;
    // strcpy(t,vals);
    vals = vals[j];
    vals[j] = t[0];
    //vals[j] = strdup(t);

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

    }
    Shalini, Jan 9, 2004
    #1
    1. Advertising

  2. Re: Find if elements of one array are present in the other and returna boolean array

    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)==0){
    > tag[j]=true;
    > // printf("%d\n",tag[j]);
    > break;
    > }
    > if(strcmp(a1[j],a2)<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, v[0])<0 && i <= r; i++) {
    > // printf("%d ",i);
    > }
    > /*for(i++; strcmp(vals, 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;
    > // strcpy(t,vals);
    > vals = vals[j];
    > vals[j] = t[0];
    > //vals[j] = strdup(t);
    >
    > }
    > while( j > i);
    > vals[j] = vals;
    > vals = 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, Jan 9, 2004
    #2
    1. Advertising

  3. Re: Find if elements of one array are present in the other and returnaboolean array

    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)==0){
    >> tag[j]=true;
    >> // printf("%d\n",tag[j]);
    >> break;
    >> }
    >> if(strcmp(a1[j],a2)<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, v[0])<0 && i <= r; i++) {
    >> // printf("%d ",i);
    >> }
    >> /*for(i++; strcmp(vals, 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;
    >> // strcpy(t,vals);
    >> vals = vals[j];
    >> vals[j] = t[0];
    >> //vals[j] = strdup(t);
    >>
    >> } while( j > i);
    >> vals[j] = vals;
    >> vals = 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
    Brian Genisio, Jan 9, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ralf Wahner
    Replies:
    5
    Views:
    629
    Bob Foster
    Dec 24, 2003
  2. Jason Heyes
    Replies:
    11
    Views:
    881
    Maxim Yegorushkin
    Jan 16, 2006
  3. J Leonard
    Replies:
    4
    Views:
    12,671
    Mark Space
    Jan 19, 2008
  4. Charanya Nagarajan
    Replies:
    6
    Views:
    130
    7stud --
    Apr 30, 2009
  5. Metre Meter
    Replies:
    7
    Views:
    367
    Metre Meter
    Aug 6, 2010
Loading...

Share This Page