Having minor problems with homework involving C bubble sort

Question

It does not work.

#include<stdio.h>

void bubble_sort(int m, int a[100000]);

void main()
{
int a[100000], i, m;
FILE * be;

be=fopen("be.txt","r");
    // IMPORTANT! i pressed enter after last number in be.txt!!!
for (i=0; !(feof(be)); ++i)
    fscanf(be,"%i", a+i);
m=i-1;
bubble_sort(m ,a);
fclose(be);

}



void bubble_sort(int m, int a[100000])
{
int i, ok, v, n=m;;
for (;!ok;ok=1)
{
    ok=0;
    for (i=0;i<=m-1;++i)
    {
        if (*(a+i)>*(a+i+1)) { v=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=v; ok=0;}
    }
    m=m-1;
}

for (i=0; i<n; ++i)
    printf("%i ", a[i]);
}

The pseudo code: (I think it`s right)

Bubblesort2( A )
m:=length( A ) - 1
repeat
    OK := true
    for i := 0 to m-1 do
        if Ai > Ai+1 then
            Ai <=>Ai+1
            OK := false
    m := m - 1
until OK

Answer 1

You aren't initialize the value of ok, so the behaviour is undefined.

You seem to be setting the value of ok to zero no matter what.

Also, there's no point optimizing bubble sort. Just get it simple and working. If you want good performance then you shouldn't be using this algorithm at all.

I'd suggest that you read the algorithm description on Wikipedia, try to write it in pseudo-code in your own words, make sure you understand it, and then implement it.

Answer 2

Try this:

void bubble_sort(int m, int a[100000])
{
    int i, ok = 0, v, n = m;
    while ( !ok )
    {
        ok = 1;
        for ( i=0; i < m-1; ++i )
        {
            if ( *(a+i) > *(a+i+1) ) 
            { 
                v = *(a+i); 
                *(a+i) = *(a+i+1); 
                *(a+i+1) = v; 
                ok = 0;
            }
        }

        m--;
    }

    for ( i = 0; i < n; ++i )
        printf("%i ", a[i]);
}

Basically, initialize ok (local variables are initialized with garbage values). You also must set ok = 1 when entering the loop and ok = 0 if a swap took place. There's no point in using a for loop, a while loop is more readable. m = m - 1 can be replaced with m--, it's the same thing and you write less code.

Answer 3

   void bubble_sort(int m, int a[])
    {
    int i, ok, v, n=m;
    for (ok = 0;!ok;)
    {
        ok=1;
        for (i=0;i<=m-1;++i)
        {
            if (*(a+i)>*(a+i+1)) { v=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=v; ok=0; }
        }
        m=m-1;
    }
    }

Two problems with your code:

1. ok was undefined at start so its not clear whether the condition on the for loop will be satisfied or not.
2. the 3rd clause (update clause) in the for statement is executed after the the code in the brackets is iterated, but before checking the condition again. So you were setting ok to 1 then checking that ok = 0. Thus it was only doing 1 iteration.

Still this program is a mess. The outer for loop should be a while loop. You should use proper array accessors a[i] rather than a+i. Also spacing and linebreaks in your source code cost nothing.