Civilization Fanatics' Forums Help with C algorithm

 Jan 06, 2007, 10:47 AM #1 Heretic_Cata We're gonna live forever     Join Date: Dec 2005 Location: Romania Posts: 9,395 Images: 5 Help with C algorithm Hi (main question in post 8) I'm trying to do a more complex version of the parallell bubble sort. I have some questions about it. I'll ask as i get to them. Here is the code: (ack, a pity spaces are ignored on the forum, the code looks kindof a mess like this ...) Spoiler: Code: ```#include #include void main() { clrscr(); int k,i,n,temp; int A[8]={1,27,3,12,56,7,1,2}; n=8; for (k=0;k<=(n-2);k++){ if(k%2==0){ for(i=0;i<=(n/2)-1;i++) if(A[2*i]>A[(2*i)+1]){ temp=A[2*i]; A[2*i]=A[2*i+1]; A[2*i+1]=temp;}} else { for(i=0;i<=(n/2)-2;i++) if(A[2*i+1]>A[2*i+2]){ temp=A[2*i+1]; A[2*i+1]=A[2*i+2]; A[2*i+2]=temp;}} } for(i=0;i
Jan 06, 2007, 11:55 AM   #2
Aphex_Twin
Evergreen

Join Date: Sep 2002
Posts: 7,476
To preserve spacing, use a [ code ] tag,
Code:
```       like
this```
First of all, try to use the more standard notation:

for (i=0; i<n; ++i)

for (i=0; i<=n-1; ++i)

(note that it's also more efficient)

Secondly, try to add accolades to the for loops (even if you only have one instruction inside).

Third, this statement:
if(k%2==0) {
can be removed. Simply modify the for loops like this:

for(i=0; i < n/2; i+=2)

and

for(i=0; i < n/2 - 1; i+=2)

This way, you don't need to test parity on each iteration, you just iterate directly through the odd or even indexed elements.

Well, I can't figure out what kind of bubble sort this is. Maybe you're looking for a thing called bidirectional or "cocktail" sort

Quote:
 There is the blunt way. If A has an odd number of elements then the last element will just search for it's place in A after the bubble sort takes place. But i don't think that's the way it should be made.
If I have an idea of how this works then if A has an odd number of elements, it won't be divided into two equal halves. The second half (I think) will have one extra element. So the last element will spend one extra iteration trying to "find" its place in the array.

I hope this helps.
__________________
[center][color="DarkBlue"][size=1]All rational action is in the first place individual action. Only the individual thinks. Only the individual reasons. Only the individual acts.
--Ludwig von Mises--

Jan 06, 2007, 12:12 PM   #3
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
^
Ok, i'll try those things a bit later ... But:
Quote:
 Originally Posted by Aphex_Twin; Well, I can't figure out what kind of bubble sort this is. Maybe you're looking for a thing called bidirectional or "cocktail" sort
It would be really funny if the teacher would say "This is not Parallell bubble sort"

I actually didn't know there was a parallel version of Bubble sort. I found it through google: lookie.
__________________
And I did cartwheels in your honour.
__________________

Jan 06, 2007, 02:16 PM   #4
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Quote:
 Originally Posted by Aphex_Twin First of all, try to use the more standard notation: for (i=0; i
You're right. And it does seem to look a bit nicer.
Quote:
 Originally Posted by Aphex_Twin Secondly, try to add accolades to the for loops (even if you only have one instruction inside).
K
Quote:
 Originally Posted by Aphex_Twin Third, this statement: if(k%2==0) { can be removed. Simply modify the for loops like this: for(i=0; i < n/2; i+=2) and for(i=0; i < n/2 - 1; i+=2) This way, you don't need to test parity on each iteration, you just iterate directly through the odd or even indexed elements.
For some unknown reason, the algorithm doesn't work correctly if i do this. It seems to order all the numbers including the one that was ommited, but it moves "7" to the 5th place in list.
Quote:
 Originally Posted by Aphex_Twin If I have an idea of how this works then if A has an odd number of elements, it won't be divided into two equal halves. The second half (I think) will have one extra element. So the last element will spend one extra iteration trying to "find" its place in the array. I hope this helps.
My God you were right. I just removed the "-1" from the second for to give it the extra iteration and it now works perfectly.
Multumesc mami.

(but the thread isn't over yet ... i have a feeling i'll stumble into some more questions a bit later ...)
__________________
And I did cartwheels in your honour.
__________________

 Jan 06, 2007, 03:51 PM #5 Heretic_Cata We're gonna live forever     Join Date: Dec 2005 Location: Romania Posts: 9,395 Images: 5 EDIT: hey, i managed to do this , nvm Ok, problem no 2. My objective now would be to make my bubble sort get data from a file. Sounds easy enough ... in Java. But in C ... One step at a time. First of all, i don't know what fuction i have to use for such a thing. From what my teacher wrote i learned how to get characters, words from files and to count integers. With functions one uglier than the other. Which is not what i need. The closest function that i would imagine getting my numbers from files would be fscanf. Is it the right one ? I tried to use it over here: Code: ```void main() { clrscr(); FILE *fp = fopen("test.txt","r"); if (fp!=NULL){ int A; fscanf(fp,"%d", A); printf("Am citit nr %d. \n", A); fclose(fp); } getch();}``` This thing should show me "2", the only thing in the test.txt file. But noooo, it seems there is a "-16329" hidden in that file, that's the result i'm getting. Also, i have another question: How does a txt file that is the source of a program supposed to look ? I mean, in Java most are like so: Code: ```31 354 677 45 47 87 42 32``` So how does the program look in the txt file for data ? __________________ And I did cartwheels in your honour. __________________ Last edited by Heretic_Cata; Jan 07, 2007 at 01:27 PM.
 Jan 08, 2007, 04:33 AM #6 Aphex_Twin Evergreen     Join Date: Sep 2002 Posts: 7,476 this line: fscanf(fp,"%d", A); change it to: fscanf(fp,"%d", &A); fscanf (and the rest of the scanf family) require the last parameters to be addresses and not variable names. &A is the address of variable A. So why does it show you -16329? Note that A is defined, but not initialized. This means A will begin its life with a gibberish value (whatever is found in memory). Since fscanf does not change the value of A, A remains uninitialized. Also, fscanf will try to write data to memory cell "-16329" and it can end up corrupting your system if you don't use an OS with memory protection (if it's Windows ME or above, you're OK). __________________ [center][color="DarkBlue"][size=1]All rational action is in the first place individual action. Only the individual thinks. Only the individual reasons. Only the individual acts. --Ludwig von Mises--
Jan 08, 2007, 05:18 AM   #7
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Quote:
 Originally Posted by Aphex_Twin this line: fscanf(fp,"%d", A); change it to: fscanf(fp,"%d", &A); fscanf (and the rest of the scanf family) require the last parameters to be addresses and not variable names. &A is the address of variable A.
Now that's one of the stupidest mistakes i ever made. After one day of doing loads of crap, i saw how it looked.
It took me almost 1 day to find that.
And after i found it, it took 5 minutes to figure out how to make a program that reads some numbers from a file, puts them in A[ ] and parallel bubble sort them.

The last part of the project will be with making parts of the program run with parallel processes. But i didn't try it yet. I'll probably have some questions on those too ...
__________________
And I did cartwheels in your honour.
__________________

 Jan 09, 2007, 02:19 PM #8 Heretic_Cata We're gonna live forever     Join Date: Dec 2005 Location: Romania Posts: 9,395 Images: 5 The wonderfull word of processes is a bit too much for me. I can't figure out what the most basic of programs do. 1. First, i have a stupid questions. What exactly are argc and argv[] ? (in general; see examples below) 2. Code: ```int main(int argc, char *argv[]) { system("dir"); }``` So, does this thing create a process by the name of "dir" ? or does it do the same thing as the "dir" command just like in cmd.exe ? 3. Code: ```int main(int argc, char *argv[]) { execlp("cmd.exe", NULL); }``` Ok, this thing executes the process in " ". So does it simply start the cmd console ? If so, then it's not working. The exemple in C help has something like: Code: `execlp("spawn.exe", NULL);` (or smthing like that) but it doesn't mention anything about spawn.exe everywhere else. (did i mention i don't know what exactly a process is ?) I'm lost. __________________ And I did cartwheels in your honour. __________________ Last edited by Heretic_Cata; Jan 09, 2007 at 02:57 PM.
Jan 09, 2007, 09:56 PM   #9
EzInKy
Excentric

Join Date: Mar 2002
Location: Kentucky
Posts: 2,887
Quote:
 Originally Posted by Heretic_Cata 1. First, i have a stupid questions. What exactly are argc and argv[] ? (in general; see examples below)
argc == the number of command line arguments.
*argv [] == a pointer to the array of the actual arguments.

Example:

Code:
```/* test_args.c */

#include <stdio.h>

int main(int argc, char *argv[])
{
int i;

printf("Number of Args: %d\n", argc);

for (i=0; i<argc; ++i)
{
printf("Arg %d: %s\n", i, argv[i]);
}

return 0;
}

\$gcc test_args.c -o test_args
\$./test_args arg1 arg2 arg3
Number of Args: 4
Arg 0: ./test_args
Arg 1: arg1
Arg 2: arg2
Arg 3: arg3```
A process is code that the operating system usually runs in its address space and can be used to launch other programs or execute tasks in the background.
__________________
Time is what keeps everything from happening all at once.

Jan 10, 2007, 04:10 AM   #10
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Quote:
 Originally Posted by EzInKy Code: ```\$gcc test_args.c -o test_args \$./test_args arg1 arg2 arg3```
What are these ?

So argv[0] will always be the path of the source file.
Argv[1] is aparently "k".
Quote:
 Originally Posted by EzInKy A process ... can be used to launch other programs or execute tasks in the background.
So ... how ?
__________________
And I did cartwheels in your honour.
__________________

Jan 10, 2007, 05:38 AM   #11
EzInKy
Excentric

Join Date: Mar 2002
Location: Kentucky
Posts: 2,887
Quote:
 Originally Posted by Heretic_Cata What are these ? So argv[0] will always be the path of the source file. Argv[1] is aparently "k".
Those are the arguments I passed to the test_args program. If you are using dos based machines the command line would like like this instead:

Code:
`C:>test_args arg1 arg2 arg3`
I was pretty sure that dos passed program arguments in the same order as Linux but it's been nearly 8 years since I've used a Microsoft OS for anything but running games that can't be emulated so I could be remembering wrong.

Quote:
 So ... how ?
First we have to be sure we are comparing apples to apples. Say I wanted to print the output of ls (dir) from my app. I'd use popen something like this:

Code:
```FILE *pipe;
char buf[80];

pipe = popen("/bin/ls", "r");
if (!pipe)
{
perror("popen");
return 1;
}

while (fgets(buf, sizeof(buf), pipe) != NULL)
{
printf("%s", buf);
pclose(pipe);
}

return 0;```
__________________
Time is what keeps everything from happening all at once.

Jan 10, 2007, 06:20 AM   #12
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Quote:
 Originally Posted by EzInKy Those are the arguments I passed to the test_args program. If you are using dos based machines the command line would like like this instead: Code: `C:>test_args arg1 arg2 arg3` I was pretty sure that dos passed program arguments in the same order as Linux but it's been nearly 8 years since I've used a Microsoft OS for anything but running games that can't be emulated so I could be remembering wrong.
Like this ?

I named the program "testarg". But for this to work doesn't there have to be an .exe ?

(I'll try your program in a bit.)
__________________
And I did cartwheels in your honour.
__________________

Jan 10, 2007, 06:39 AM   #13
EzInKy
Excentric

Join Date: Mar 2002
Location: Kentucky
Posts: 2,887
Quote:
 Originally Posted by Heretic_Cata Like this ? I named the program "testarg". But for this to work doesn't there have to be an .exe ? (I'll try your program in a bit.)
Yes there has to be an executable file to run the program, and if I remember right dos does use extensions such as .exe, .com, etc..., instead of determining type by actually looking at what is in the file.
__________________
Time is what keeps everything from happening all at once.

Jan 10, 2007, 06:51 AM   #14
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Code:
```FILE *pipe;
char buf[80];

pipe = popen("/bin/ls", "r");
if (!pipe)
{
perror("popen");
return 1;
}

while (fgets(buf, sizeof(buf), pipe) != NULL)
{
printf("%s", buf);
pclose(pipe);
}

return 0;```
C Help doesn't seem to have heard of popen/pclose. Do you mean fopen/fclose ? (but those are for opening a data file ... they can't work)

Quote:
 Originally Posted by EzInKy Yes there has to be an executable file to run the program, and if I remember right dos does use extensions such as .exe, .com, etc..., instead of determining type by actually looking at what is in the file.
I tried with
"testarg.exe arg1 arg2 arg3" - that didn't work either.

But i have heard that it is possible to create an exe of your source code. Someone did it for my pacman program. But i can't find anything in my Borlandc that can do that. I don't know how he did it, and he's not going to be around for a while so i don't know who to ask.
__________________
And I did cartwheels in your honour.
__________________

Jan 10, 2007, 06:58 AM   #15
EzInKy
Excentric

Join Date: Mar 2002
Location: Kentucky
Posts: 2,887
Quote:
 Originally Posted by Heretic_Cata I tried with "testarg.exe arg1 arg2 arg3" - that didn't work either. But i have heard that it is possible to create an exe of your source code. Someone did it for my pacman program. But i can't find anything in my Borlandc that can do that. I don't know how he did it, and he's not going to be around for a while so i don't know who to ask.
You mean you haven't compiled the program yet?
__________________
Time is what keeps everything from happening all at once.

Jan 10, 2007, 07:01 AM   #16
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Quote:
 Originally Posted by EzInKy You mean you haven't compiled the program yet?
You mean:
Alt+F9 = compile
and
Ctrl+F9 = run
?

Of course i did that. But they don't create exe files.
__________________
And I did cartwheels in your honour.
__________________

Jan 10, 2007, 07:13 AM   #17
EzInKy
Excentric

Join Date: Mar 2002
Location: Kentucky
Posts: 2,887
Quote:
 Originally Posted by Heretic_Cata You mean: Alt+F9 = compile and Ctrl+F9 = run ? Of course i did that. But they don't create exe files.
Seems we are talking two different languages here, lol. It's been a really long time since I've used a borland ide, but those shortcuts do sound familiar. Do this...go back to your command line and type...

Code:
`C:>bcc32 TestArgs.cpp`
...and see if you don't get an executable.
__________________
Time is what keeps everything from happening all at once.

Jan 10, 2007, 07:26 AM   #18
Heretic_Cata
We're gonna live forever

Join Date: Dec 2005
Location: Romania
Posts: 9,395
Images: 5
Quote:
 Originally Posted by EzInKy Seems we are talking two different languages here, lol. It's been a really long time since I've used a borland ide, but those shortcuts do sound familiar. Do this...go back to your command line and type...
I've heard that in newer versions, exe's are created automatically.
Quote:
 Code: `C:>bcc32 TestArgs.cpp` ...and see if you don't get an executable.
Nope that's not it. But a friend of mine who knows pascal told me how.
In the menus there is a "Build all" option. I've clicked it before, but i never looked what it was doing. It created an exe in a far away folder.
I'll try all the stuff now.
__________________
And I did cartwheels in your honour.
__________________

 Jan 10, 2007, 07:40 AM #19 EzInKy Excentric     Join Date: Mar 2002 Location: Kentucky Posts: 2,887 "Build all"...that was it. There is a program called Rhide that has the look and feel of the old Borland IDE that has been ported to Linux but I don't have it installed. I find it easier to use the command line when you are writing small programs. __________________ Time is what keeps everything from happening all at once.
 Jan 10, 2007, 07:52 AM #20 Heretic_Cata We're gonna live forever     Join Date: Dec 2005 Location: Romania Posts: 9,395 Images: 5 Yup, the first one worked perfectly. I understand it. Now on to the next question: Code: ```FILE *pipe; char buf[80]; pipe = popen("/bin/ls", "r"); if (!pipe) { perror("popen"); return 1; } while (fgets(buf, sizeof(buf), pipe) != NULL) { printf("%s", buf); pclose(pipe); } return 0;``` About your code ... C Help doesn't seem to have heard of popen/pclose. Do you mean fopen/fclose ? (but those are for opening a data file ... they can't work) (i also changed "ls" to "dir" in my code) __________________ And I did cartwheels in your honour. __________________

 Bookmarks

 Civilization Fanatics' Forums > Help with C algorithm