Progress of a Bubble Sort (C)

Since you hash define NUM_ITEMS, you don't really need to pass it to functions.

Since you hash define NUM_ITEMS, you don't really need to pass it to functions.

What if the caller wants to use something other than NUM_ITEMS without redefining it? Passing the size provides greater flexibility, and just because you can do something doesn't mean you should. You can use NUM_ITEMS all over creation, but that doesn't mean it's a good idea.

good

True, this is properly a better and more flexible solution, just pointed it out.

Wouldn't it be even more efficient, if you calculated the size of the array inside the functions? Since in almost every case, you wouldn't want the array_size to differ from the actual size of the array.

Wouldn't it be even more efficient, if you calculated the size of the array inside the functions?

Aside from not being possible without enforcing some kind of structure to the array that allows calculation of its size, calculating something that's not calculated originally would be less efficient.

Since in almost every case, you wouldn't want the array_size to differ from the actual size of the array.

That's not really the function's problem. If the caller lies to it, there's really nothing it can do. Also, it would be more flexible if you don't require the size to match the size of the array because you might want to perform a partial sort:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubblesort(int a[], int begin, int end)
{
    for (int i = begin; i < end; i++) {
        int done = 1;

        for (int j = end - 1; j > begin; j--) {
            if (a[j] < a[j - 1]) {
                swap(&a[j], &a[j - 1]);
                done = 0;
            }
        }

        if (done) {
            break;
        }
    }
}

void show(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        printf("%4d", a[i]);
    }

    puts("");
}

int main(void)
{
    int a[N];

    srand((unsigned)time(NULL));

    for (int i = 0; i < N; i++) {
        a[i] = rand() % 100;
    }

    show(a, N);

    /* Sort the two halves separately */
    bubblesort(a, 0, 5);
    bubblesort(a, 5, N);

    show(a, N);

    return 0;
}

This kind of behavior is the bread and butter of other algorithms like quicksort or mergesort. One notable optimization of quicksort is to use something less heavy like insertion sort when the subarray gets small enough that the lighter sort is faster. If the lighter sort is written to work on the array as a whole, you can't use it for that purpose.

wow... I don't really know what to say. I just thought that you could use "sizeof(numbers)" until i realize that is gonna give you the number of bytes. And that you wouldn't want the array_size to be bigger, because of the risk of overflowing it, I didn't even think about sorting parts of the array. Think I will go back to learning some more, before posting.

I am new to c, and I prefer using loop as the following code . Is there any questions ?

void bubblesort( int num[], int arraysize )
{
    bool flag_finished = false;

    //loop 
    while( flag_finished== false )
    {
        flag_finished = true ;

        //one time sort
        for( int i=0;i<arraysize; i++ )
             {
                 if( i== arraysize-1 )
                 {
                     break;
                 }

                 if( num[i]< num[i+1])
                 {
                     int tmp = num[i]  ;
                     num[i]  = num[i+1];
                     num[i+1]= tmp    ;

                     flag_finished =false;
                 }
             }

             show(num, arraysize );
    }

    //end
}

Sure you can use a while loop, but you have to be carefull not to end up in an endless loop.

Print %, as 100*(sorted size/total size)^2, since simple bubble sort effort is n^2 scaled.

Since this thread has been a little resuscitated ...

it may be the case that some beginning students in C ...

might like to know ...

that a simple bubble sort (usually used ONLY on very small data sets - arrays)

can be used effectively on a very large data set - array ...

*** IF ***

the collection is already sorted and a new element is added (at the end) ...

*** and IF THEN ***

the bubble sort ... then bubbles from the rear to the front.

/* bubble_sort2.h */

#ifndef BUBBLE_SORT2_H
#define BUBBLE_SORT2_H

#ifndef shaker_sort
#define shaker_sort 0
#endif

#ifndef back_to_front
#define back_to_front 1
#endif

#ifndef show_steps
#define show_steps 0
#endif


#if back_to_front

/* Iter's here are 'BI-DIRECTINAL' ... 
   (i.e. can traverse in both directions)
   This bubble-sort, bubbles from 'back-to-front' ... 
   so can call after a 'push_back' to stay sorted ... */
void bubble_sort( Iter beg, Iter end,  int (*cmp) (const void* a, const void* b) )
{
    /* so can stop if reach 'one before begin' */
#if show_steps
    Iter sav_beg = beg, sav_end = end;
#endif
    Iter right_el = --end;
    Iter left_el = right_el;

    int aswap = 1;
    --beg;
    while( aswap )
    {
#if show_steps
        putchar('\n');
#endif
        aswap = 0;
        while( --left_el != beg )
        {
            /* Note right, left order below ... when doing bubble_sort */
            if( cmp( right_el, left_el) < 0 ) /* Ok ... swap values */
            {
                MyType tmp = *left_el;
                *left_el = *right_el;
                *right_el = tmp;

                /* was a swap ... so UP date swap flag value ... */
                aswap = 1;
            }
            --right_el;
#if show_steps
            show(  sav_beg, sav_end-sav_beg );
#endif
        }

        ++beg ;  /* get ready for next loop; note 'beg' IS now 'sorted' */
# if !shaker_sort
        left_el = right_el = end;  /* start at end if need a next loop */
#else
        if( aswap )
        {
            left_el = right_el = beg; /* start at front if need a next loop */
#if show_steps
            putchar('\n');
#endif
            aswap = 0;
            ++end;
            while( ++right_el != end )
            {
                /* Note right, left order below ... when doing bubble_sort */
                if( cmp( right_el, left_el) < 0 ) /* Ok ... swap values */
                {
                    MyType tmp = *left_el;
                    *left_el = *right_el;
                    *right_el = tmp;

                    /* was a swap ... so UP date swap flag value ... */
                    aswap = 1;
                }
                ++left_el;
#if show_steps
                show( sav_beg, sav_end-sav_beg );
#endif
            }

            --end; /* get ready for next loop; note 'end' IS now 'sorted' */

            left_el = right_el = end; /* start at beg if need a next loop */
        }
#endif
    }
}



#else /*  NOT 'back_to_front'  ... so bubble sort ... front to back */



/* Iter's are 'BI-DIRECTINAL' ... so can traverse in both directions ... */
void bubble_sort( Iter beg, Iter end,  int (*cmp) (const void* a, const void* b) )
{
    Iter left_el = beg, right_el = beg;
#if show_steps
    Iter sav_beg = beg, sav_end = end;
#endif

    int aswap = 1;;
    while( aswap )
    {
#if show_steps
        putchar('\n');
#endif
        aswap = 0;
        while( ++right_el != end )
        {
            /* Note right, left order below ... when doing bubble_sort */
            if( cmp( right_el, left_el) < 0 ) /* Ok ... swap values */
            {
                MyType tmp = *left_el;
                *left_el = *right_el;
                *right_el = tmp;

                /* was a swap ... so UP date swap flag value ... */
                aswap = 1;
            }
            ++left_el;
#if show_steps
            show(  sav_beg, sav_end-sav_beg );
#endif
        }

        /* here is why we want bidirectional iter's */
        --end;  /* get ready for next loop; note 'end' IS now 'sorted' */
# if !shaker_sort
        left_el = right_el = beg;  /* start at beg if need a next loop */
#else
        --end;
        left_el = right_el = end; /* start at end if need a next loop */
        if( aswap )
        {
#if show_steps
            putchar('\n');
#endif
            aswap = 0;
            --beg;
            while( --left_el != beg )
            {
                /* Note right, left order below ... when doing bubble_sort */
                if( cmp( right_el, left_el) < 0 ) /* Ok ... swap values */
                {
                    MyType tmp = *left_el;
                    *left_el = *right_el;
                    *right_el = tmp;

                    /* was a swap ... so UP date swap flag value ... */
                    aswap = 1;
                }
                --right_el;
#if show_steps
                show( sav_beg, sav_end-sav_beg );
#endif
            }

            ++beg; /* get ready for next loop; note 'beg' IS now 'sorted' */

            left_el = right_el = beg; /* start at beg if need a next loop */
        }
#endif
    }
}

#endif /* END ' '#if back_to_front */


#endif

Here is a little test program:

/* test_bubble_sort2.c */


#include <stdio.h>


#define show_steps 1 /* set to 0 to 'turn off' */
#define shaker_sort 0 /* set to 1 to see 'shaker_sort */


typedef int MyType;
typedef MyType* Iter;


/* global count re. count of lines printed ... */
int count = 0;

/* used also in show steps ... */
void show( const MyType ary[], int ary_size )
{
    int i;
    printf( "Line %2d: ", ++count );
    for( i = 0; i < ary_size; ++ i )
        printf( "%2d ", ary[i] );
    putchar( '\n' );
}


/* NOW can include this ... */
#include "bubble_sort2.h"


int myCmp( const void* a, const void* b )
{
    return *(const int*)a  - *(const int*)b;
}





int main()
{
    MyType ary[] = /* { 8, 10, 6, 7, 4, 5, 9, 1, 3, 2 }; */  { 1,2,3,4,5,6,7,8,9,0 };
    const int size = sizeof ary / sizeof *ary ;

    bubble_sort( ary, ary+size, myCmp );

    puts( "After sorting ... " );
    show( ary, size );
    return 0;;
}

If you'd like to see a 'dynamic C array' (a Cvec) of dynamic C struct holding dynamic C strings ...

and a bubble sort being used to keep added id's ... UNIQUE ...
(by using a binary search) ...

see the following demo.

Note that the example uses the files readLine.h and Cvec.h available here:
readLIne/h
http://developers-heaven.net/forum/index.php/topic,2580.msg2864.html#msg2864
Cvec.h
http://developers-heaven.net/forum/index.php/topic,2580.msg2862.html#msg2862

/* test_bubble_sort2_with_Cvec.c */

#include "readLine.h"


typedef struct myRecord
{
    char* name;
    int id;
} Rec ;

void freeVrec( Rec* p )
{
    free( p->name ); /* to free dynamic C string memory */
}

/* AFTER above 2 definitions ... can THEN include this ... */
#include "Cvec.h"


typedef Rec MyType;
typedef MyType* Iter;


/* global line print count */
/* int count = 0; */

/* NOW can ... */
#include "bubble_sort2.h"

/* for ascending sort ... */
int myCmpId( const void* a, const void* b )
{
    return ((const Iter)a)->id - ((const Iter)b)->id ;
}

int myCmpName( const void* a, const void* b )
{
    int val = strcmp( ((const Iter)a)->name,  ((const Iter)b)->name ) ;
    if( val == 0 ) return ((const Iter)a)->id - ((const Iter)b)->id ;
    else return val;
}

void showRec( const Rec* rc )
{
    printf( "(%05d, %s)\n", rc->id, rc->name );
}
void showCvec( const Cvec* cv )
{
    int i;
    for( i = 0; i < cv->size; ++ i )
        showRec( &cv->ary[i] );
}

/* 3 utilities to ease codong here ... */
int takeInChr( const char* msg )
{
    int reply;
    fputs( msg, stdout ); fflush( stdout );
    reply = getchar();
    if( reply != '\n' )
        while( getchar() != '\n' ) ; /* 'flush' stdin buffer */
    return reply;
}

int more() /* defaults to 'true'/'yes'/'1' ... unless 'n' or 'N' entered */
{
    if( tolower( takeInChr( "More (y/n) ? " )) == 'n' ) return 0;
    /* else ... */
    return 1;
}

char* takeInStr( const char* msg )
{
    fputs( msg, stdout ); fflush( stdout );
    return readLine( stdin );
}


/* recursive ... returns index 'target int val found ... or -1 ... */
int rBinarySearch( const Cvec* cv, int low, int high, int target )
{
    int mid;

    if( high < low ) return -1; /* NOT found FLAG VALUE ... */

    mid = low + ( ( high - low ) >> 1 ); /*  ( low + hign ) / 2   */

    if( target < cv->ary[mid].id ) return rBinarySearch( cv, low, mid - 1, target );
    /* else if ... */
    if( target > cv->ary[mid].id ) return rBinarySearch( cv, mid + 1, high, target );
    /* else ... */
    return mid; /* FOUND at this index = mid */
}

void takeInRec( Cvec* cv, Rec* rc )
{
    for( ; ; ) /* loop to ensure unique id ... */
    {
        int found;
        char* tmp = takeInStr( "Enter integer id :  ");
        rc->id = atoi(tmp);
        found = rBinarySearch( cv, 0, cv->size-1, rc->id );
        free( tmp );
        if( found == -1 )
        {
            if( rc->id > 0 && rc->id <= 99999 ) break;
            else puts( "Valid range is: 1..99999" );
        }
        else
            printf( "That id: (%05d) is already taken ... \n", rc->id );
    }
    rc->name = takeInStr ( "Enter name       :  " );
}




int main()
{
    Rec rc;
    Cvec cv;
    initCvec( &cv ); /* MuST initial to use ok ... */

    do
    {
        takeInRec( &cv, &rc );
        push_backCvec( &cv, &rc );
        bubble_sort( &cv.ary[0], &cv.ary[cv.size], myCmpId );
    }
    while( more() );

    puts( "After data entry ... " );
    showCvec( &cv );

    bubble_sort( &cv.ary[0], &cv.ary[cv.size], myCmpName );

    puts( "After sorting by name ... " );
    showCvec( &cv );

    bubble_sort( &cv.ary[0], &cv.ary[cv.size], myCmpId );

    puts( "After sorting by id ... " );
    showCvec( &cv );

    clearCvec( &cv );
    return 0;;
}

From the bubble sort you can evolve to many other in memory sorts.

A simple speedup would be to use bisection search the sorted list for the insert point.

One that works well to optimize cache locality of reference is to consider the array as n sorted lists of 1 item, merge the list in a binary fashion, 1 to 2, 3 to 4, 1+2 to 3+4, 5 to 6, 7 to 8, 5+6 to 7+8, 1+2+3+4 to 5+6+7+8, .... You can use the current count bits to tell you what to do next. Since you are referencing small sets then larger, doubling as you go, it gracefuly shifts from l1 cache speed to l2 cache speed to RAM row-page speed to RAM many-row speed to disk (VM) speed.

Other sorts exploit sorted data well, treating input a n sets of sorted data to be discovered, then merged, on disk/vm perhaps shortest to longest, so you merge to long sets the least number of times. If the data is sorted, that is discovered on the first pass. If the data is one item and a sorted list of n-1 items, finding the insertion point serially is costly.

In practice, all systems have APIs available that sort, such as the tree list tsearch() http://linux.die.net/man/3/tsearch, qsort() http://linux.die.net/man/3/qsort or OO containers that sort like JAVA TreeMap Class Template https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html or C++ STL map: http://www.sgi.com/tech/stl/Map.html

You can also popen() http://linux.die.net/man/3/popen a sort http://linux.die.net/man/1/sort and let it do the heavy lifting. You can have the sort write output to a named pipe, and once you write and close the input popen() pipe, you can open the named pipe to stream the result in. The 'sort' must read the last item in before it can write the first item out. The popen() cmd argument can create the named pipe (FIFO) http://linux.die.net/man/1/mknod, call the sort, and remove the named pipe. Since the sort will not end until your read the last output item, it is immediately safe to remove the named pipe.