Thread: help with debug (bubble sort algorithm)

  1. #1
    Registered User
    Join Date
    Sep 2007
    Location
    Reggio Emilia, Italy
    Posts
    15

    help with debug (bubble sort algorithm)

    hello, I'm trying to write a version of bubble sort with some
    improvement.

    One of these is that at the end of every pass, the algorithm
    compare the array before and after the bubble sort; if they are
    equal it stops; otherwise it execute bubble sort again


    Code:
    
    #include <stdio.h>
    #include <assert.h>
    
    
    void bubble_sort(int array[], int array_length);
    void print_array(int array[], int array_length);
    int are_different(int array_a[], int array_b[], int common_length);
    
    
    
    int main( void )
    {/*************/
       int a[] = {3,1,4,2};
    
       print_array(a,4);
       bubble_sort(a,4);
       print_array(a,4);
    
       return 0;
    }
     
    
    void bubble_sort(int array[], int array_length)
    {/********************************************/
    
       int pass;                    /* pass counter */
       int i;                       /* vector index */
       int hold;                    /* temporary location */
    
       /* A copy of the original array for future
        * comparison with modified versions */
    
       int orig_array[array_length];
    
       for ( pass = 1; pass < array_length; pass++ )
          {
    
             for ( i=0 ; i < array_length; i++ )
                orig_array[i] = array[i];
    
             /* here the first change, with 1 substitueted by pass,
             in order to diminish the comparison with pass
             increasing*/
             for ( i = 0; i < array_length - pass; i++ )
                {
    
                   if ( array[ i ] > array[ i + 1 ] )
                      {
                         hold = array[ i ];
                         array[ i ] = array[ i + 1 ];
                         array[ i + 1 ] = hold;
    
                      }
                }
    
    
             /* here the decision to continue or not, based on
             "modified" dummy */
    
             assert(are_different(orig_array, array, array_length));
    
             if (are_different(orig_array, array, array_length))
                /* if modified execute it again */
                continue;
             else
                break;              /* if not modified exit */
          }
    
    }
    
    
    int are_different(int array_a[], int array_b[], int common_length)
    {/***************************************************************/
    
       int i;
    
       for (i = common_length -1; i = 0; i--)
          {
             if (array_a[i] != array_b[i])
                return 1;
          }
       return 0;
    
    
    }
    
    
    
    void print_array(int array[], int array_length)
    {/********************************************/
    
       int index;
    
       for (index = 0; index < array_length ; index++)
          printf("%3d ", array[index]);
    
       printf("\n");
    
    }
    I can't get are_different(orig_array, array, array_length) to be 1, and don't see why

    Code:
    $: ./a.out 
      3   1   4   2 
    a.out: bubble_sort.c:63: bubble_sort: Assertion `are_different(orig_array, array, array_length)' failed.
    Aborted

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Surely this is a failed attempt to "optimise" the bubblesort. Why not just have a flag that you set if you change something, rather than comparing your arrays. Copying and comparing arrays is a complete waste of time here.

    Code:
       for (i = common_length -1; i = 0; i--)
    If you only do the loop when the red bit is true, then it will never enter the loop. Even if you change it to i == 0;, it would still only enter the loop if you have common_length == 1, so probably not quite what you want.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Location
    Reggio Emilia, Italy
    Posts
    15
    Quote Originally Posted by matsp View Post
    Surely this is a failed attempt to "optimise" the bubblesort. Why not just have a flag that you set if you change something, rather than comparing your arrays. Copying and comparing arrays is a complete waste of time here.
    You're right, this's surely not the better way to improve the algorithm ( and I know this is a useless function, since one can use qsort from libc), but if you mean I need pointers, I have not studied them, yet (I know vaguely what they're). The exercise is at the end of the chapter before the pointers one, so is there another way to do what you mean not using comparison beetween array?


    Quote Originally Posted by matsp View Post
    Code:
       for (i = common_length -1; i = 0; i--)
    If you only do the loop when the red bit is true, then it will never enter the loop. Even if you change it to i == 0;, it would still only enter the loop if you have common_length == 1, so probably not quite what you want.

    --
    Mats
    yes I've tried to correct as follows, but it doesn't work yet


    Code:
    #include <stdio.h>
    #include <assert.h>
    
    
    void bubble_sort(int array[], int array_length);
    void print_array(int array[], int array_length);
    int are_they_different(int array_a[], int array_b[], int common_length);
    
    
    int main( void )
    {/*************/
       int a[] = {3,1,4,2};
    
       print_array(a,4);
       bubble_sort(a,4);
       print_array(a,4);
    
       return 0;
    }
    
    
    void bubble_sort(int array[], int array_length)
    {/********************************************/
    
       int pass;                    /* pass counter */
       int i;                       /* vector index */
       int hold;                    /* temporary location */
    
       /* A copy of the original array for future                                
        * comparison with modified versions */
    
       int orig_array[array_length];
    
       for ( pass = 1; pass < array_length; pass++ )
          {
    
             for ( i=0 ; i < array_length; i++ )
                orig_array[i] = array[i];
    
             /* here the first change, with 1 substitueted by pass,              
             in order to diminish the comparison with pass                       
             increasing*/
    
             for ( i = 0; i < array_length - pass; i++ )
                {
                   if ( array[ i ] > array[ i + 1 ] )
                      {
                         hold = array[ i ];
                         array[ i ] = array[ i + 1 ];
                         array[ i + 1 ] = hold;
    
                      }
                }
    
    
             /* here the decision to continue or not*/
    
             assert(are_they_different(orig_array, array, array_length));
    
             if (are_they_different(orig_array, array, array_length))
                /* if modified execute it again */
                continue;
             else
                break;              /* if not modified exit */
          }
    
    }
     
    
    int are_they_different(int array_a[], int array_b[], int common_length)
    {/***************************************************************/
    
    
       int i;
    
       for (i = common_length - 1; i >= 0; i--)
          {
             if (array_a[i] != array_b[i])
                return 1;
          }
       return 0;
    
    
    }
    
    
    
    void print_array(int array[], int array_length)
    {/********************************************/
    
       int index;
    
       for (index = 0; index < array_length ; index++)
          printf("&#37;3d ", array[index]);
    
       printf("\n");
    
    }
    gcc ...


    Code:
    $: ./a.out 
      3   1   4   2 
    a.out: bub_comparison.c:63: bubble_sort: Assertion `are_they_different(orig_array, array, array_length)' failed.
    Aborted
    They should be different, because original array is unsorted and bubble sort works as expected. Why it's not so?

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Print the array after each iteration and you should see that the array is already sorted before the last iteration (which won't change anything). You can't avoid a test iteration to see if it is already sorted, so the assert is simply out of place.

    You're right, this's surely not the better way to improve the algorithm ( and I know this is a useless function, since one can use qsort from libc)
    I think you misunderstood: you are not necessarily improving the algorithm at all. Simply put a flag in which you change if something gets swapped at all during each iteration.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You know this is a complete waste of time and actually makes it slower don't you?
    All you need to do is set a flag if the pass makes any changes, or better yet, track where each bubble is pushed to on each pass.

    My website (see my sig) shows what I'm talking about.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Sep 2007
    Location
    Reggio Emilia, Italy
    Posts
    15
    Quote Originally Posted by anon View Post
    Print the array after each iteration and you should see that the array is already sorted before the last iteration (which won't change anything). You can't avoid a test iteration to see if it is already sorted, so the assert is simply out of place.

    Thank you all (matsp iMalc, anon ), I have fixed my bug and now bubble sort "rocks".

    This made me reflect that I have to take a further look at variables memory class and visibility rules (a previous version was somewhat similar to flag one but I abandoned it because of some untrue credencies about visibility rules... )

    Quote Originally Posted by anon View Post
    I think you misunderstood: you are not necessarily improving the algorithm at all. Simply put a flag in which you change if something gets swapped at all during each iteration.
    I knew more computation was requested, I used "improve" too generously since a modification of that kind ameliorate execution of the sort (comparing with execution without flag and without comparison) 1 time on 100 (when an array get perfectly sorted in 1 pass... maybe)... most of the times it slows sorting process


    Thanks again

    ps If I've wrote some silly thing, please let me know!
    Last edited by lbraglia; 10-19-2007 at 05:53 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bubble sort not working... wats d prob?
    By Huskar in forum C Programming
    Replies: 8
    Last Post: 03-31-2009, 11:59 PM
  2. My bubble sort only sorts once
    By Muller in forum C Programming
    Replies: 8
    Last Post: 03-27-2009, 04:36 PM
  3. choosing right sort algorithm
    By Micko in forum C++ Programming
    Replies: 15
    Last Post: 05-29-2006, 10:38 AM
  4. Array/Structure Bubble Sort
    By JKI in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2003, 11:59 AM
  5. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM