c - Strange things happen when swapping two vars in QuickSort -
i'm implementing quicksort in c.
here's swap procedure:
void swap(int *x, int *y) { *x += (*y); *y = (*x) - (*y); *x = (*x) - (*y); }
and here's partition procedure:
int partition(int a[], int sx, int dx) { int indice_pivot = (rand()%(dx-sx+1))+sx; int = sx-1, j; swap(&a[indice_pivot],&a[dx]); for(j=sx;j<dx;j++) { if(a[j] <= a[dx]) { i++; swap(&a[j],&a[i]); } } i++; swap(&a[i],&a[dx]); return i; }
the problem when swapping 2 variables, magically (?) become 0. did debugging , seems working fine inside swap procedure. array contains zeros @ end of partitions (not of them). strange thing if replace swap procedure
void swap(int *x, int *y) { int temp = *y; *y = *x; *x = temp; }
everything works fine. why?
your swap function not work if both pointers point same element. if second step *y = (*x) - (*y);
sets element 0, since equivalent *x = (*x) - (*x);
the second swap function temp variable preserves values.
at glance looks swap(&a[indice_pivot],&a[dx]);
hitting same element. can use assert( indice_pivot != dx )
determine that( or of course put 1 in swap function ).
Comments
Post a Comment