Help with C algorithm

[Heretic_Cata]

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:

#include <stdio.h>
#include <conio.h>

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<n;i++){
	printf("%d\n",A[i]);}
getch();
}

Please excuse the noobness of my skills.

The thing is when A[ ] has an odd number of elements in it, the algorithm doesn't use the last one.
The way i figure, the n/2 is to blame, but i can't find a way to fix it. How could i do it in a "subtle" way ?

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.

[Aphex_Twin]

To preserve spacing, use a [ code ] tag,

       like
              this

First of all, try to use the more standard notation:

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

instead of:

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

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.

[Heretic_Cata]

^
Ok, i'll try those things a bit later ... But:

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.

[Heretic_Cata]

Originally Posted by Aphex_Twin

First of all, try to use the more standard notation:
for (i=0; i<n; ++i)
instead of:
for (i=0; i<=n-1; ++i)
(note that it's also more efficient)

You're right. And it does seem to look a bit nicer.

Originally Posted by Aphex_Twin

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

K

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.

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

[Heretic_Cata]

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:

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:

31  354  677  45
47  87  42  32

So how does the program look in the txt file for data ?

[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.


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

[Heretic_Cata]

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

[Heretic_Cata]

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.

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.

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:

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.

[EzInKy]

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:

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

[Heretic_Cata]

Originally Posted by EzInKy

$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".

Originally Posted by EzInKy

A process ... can be used to launch other programs or execute tasks in the background.

So ... how ?

[EzInKy]

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:

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.

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:

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;

[Heretic_Cata]

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:

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

[EzInKy]

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.

[Heretic_Cata]

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)

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.

[EzInKy]

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?

[Heretic_Cata]

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.

[EzInKy]

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

C:>bcc32 TestArgs.cpp

...and see if you don't get an executable.

[Heretic_Cata]

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.

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.

[EzInKy]

"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.

[Heretic_Cata]

Yup, the first one worked perfectly. I understand it.

Now on to the next question:

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)