Hi ,
Is the code below efficient??
bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){
charQuickSort(a 2, 0, (lengtha2-1));
bool *tag=(bool*)cal loc(lengtha1,si zeof(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",t ag[j]);
break;
}
if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){
tag[j] = false;
// printf("%d\n",t ag[j]);
break;
}
}
}
return(tag);
}
void charQuickSort(c har **vals, int l, int r)
{
int i,j,m;
char **v=(char **)calloc(1,siz eof(char *));
char **t=(char **)calloc(1,siz eof(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(v als, l, i-1);
charQuickSort(v als,i+1,r);
}
} 2 1566
Shalini wrote: Hi , Is the code below efficient??
bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){ charQuickSort(a 2, 0, (lengtha2-1)); bool *tag=(bool*)cal loc(lengtha1,si zeof(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",t ag[j]); break; } if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){ tag[j] = false; // printf("%d\n",t ag[j]); break; } } }
return(tag); }
void charQuickSort(c har **vals, int l, int r) { int i,j,m; char **v=(char **)calloc(1,siz eof(char *)); char **t=(char **)calloc(1,siz eof(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(v als, l, i-1); charQuickSort(v als,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 wrote: Shalini wrote:
Hi , Is the code below efficient??
bool *isElement(char **a1,long lengtha1,char **a2,long lengtha2){ charQuickSort(a 2, 0, (lengtha2-1)); bool *tag=(bool*)cal loc(lengtha1,si zeof(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",t ag[j]); break; } if(strcmp(a1[j],a2[i])<0 || (i == (lengtha2-1))){ tag[j] = false; // printf("%d\n",t ag[j]); break; } } }
return(tag); }
void charQuickSort(c har **vals, int l, int r) { int i,j,m; char **v=(char **)calloc(1,siz eof(char *)); char **t=(char **)calloc(1,siz eof(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(v als, l, i-1); charQuickSort(v als,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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Psybar Phreak |
last post by:
hi all
i have an array of Process objects, each elements has an id (process.id),
and arrival time (process.at), processing time (process.pt) and a boolean
indicating whether the process has completed (process.done).
atm, i have a loop that i going through the elements and check whether each
elements has been done, i am now at a point in the loop, where it has
discovered, that the current process (currentProcess) is done (ie....
|
by: Madestro |
last post by:
Hi guys,
I am making a small program to retrieve e-mails from POP accounts. I got all
the e-mail parsing stuff figured out, but I cannot seem to come up with a way
to find out which e-mails are NEW so I don't have to retrieve them all. If
you have experience with this kind of thing, you know that the server creates
unique IDs for all the messages, but this IDs are not guaranteed to be
unique, since they can be reused once a message is...
|
by: Massimiliano Alberti |
last post by:
Can someone check this? If it's OK, you can use however you want... :-)
It should search for an element in an array and, if it can't find it, return
the next element.
key is what you are searching, in a *base array of LONG with num elements.
After some tests it seems to work well (the original version was filled with
ASSERTs)
(I will use this function in a bigger look-for-or-insert function)
Some notes:
The function returns the index...
|
by: Busin |
last post by:
bool arr;
arr = true;
For the element arr, is there any fastest algorithm to fast find the two
elements on both side of "n" and both elements are cloest to "23"?
Thanks!
|
by: Stacey Levine |
last post by:
I have a webservice that I wanted to return an ArrayList..Well the service
compiles and runs when I have the output defined as ArrayList, but the WSDL
defines the output as an Object so I was having a problem in the calling
program. I searched online and found suggestions that I return an Array
instead so I modified my code (below) to return an Array instead of an
ArrayList. Now I get the message when I try to run just my webservice...
| |
by: Charles Law |
last post by:
I have a complex object that I am serializing, and I would like to omit
elements that have a default value.
For example, if I have a class as follows
Public Class Test
Private m_Name As String = "George"
Private m_Active As Boolean = False
Private m_Address As String
|
by: Tuxedo |
last post by:
I'd like to reorganize the third, fourth, fifth and sixth, as well as any
elements thereafter in an array in random order:
var a = new Array('first','second','third','fourth','fifth','sixth','etc')
In other words, the first, second and third element should remain in
position 0, 1 and 2, while the fourth, fifth and sixth, etc. should appear
in random order.
Can anyone recommend a method to do this?
|
by: C C++ C++ |
last post by:
Hi all, got this interview question please respond.
How can you quickly find the number of elements stored in a a) static
array b) dynamic array ?
Rgrds
MA
|
by: ALKASER266 |
last post by:
Hey guyz
I have a prac and I am beginner and I did this code>
Is my code is complete and if is it not complete how i can complete it?
and how i can arrange it more?
How I can make my driver to an array that generates an array of 20 students instead of my way of driver to enter it manually? THANK YOU VERY MUCH
I will put the question then I will put my answer
It is two codes one is Student which is the main one and the other one is...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| |
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |