help with debug (bubble sort algorithm)

• 10-19-2007
lbraglia
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```
• 10-19-2007
matsp
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
• 10-19-2007
lbraglia
Quote:

Originally Posted by matsp
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
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 ... :eek:

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? :confused:
• 10-19-2007
anon
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.

Quote:

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.
• 10-19-2007
iMalc
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.
• 10-19-2007
lbraglia
Quote:

Originally Posted by anon
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
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! :)