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

---

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

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:

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.

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.

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! :)