Strange things happen when replacing two vars in QuickSort

Question

I am using QuickSort in C.

Here is my swap procedure:

void swap(int *x, int *y) { *x += (*y); *y = (*x) - (*y); *x = (*x) - (*y); } 

And here is my section procedure:

 int partition(int a[], int sx, int dx) { int indice_pivot = (rand()%(dx-sx+1))+sx; int i = 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 is that when replacing two variables they magically (?) Become 0. I did some debugging and everything seems to work fine in the swap procedure. But the array contains zeros at the end of some sections (not all of them). It is strange that if I replaced the swap procedure with

 void swap(int *x, int *y) { int temp = *y; *y = *x; *x = temp; } 

Everything works perfectly. Why?

Answer 1

Your swap function will not work if both pointers point to the same element. If they perform the second step *y = (*x) - (*y); , sets the element to 0, since it is equivalent to *x = (*x) - (*x);

The second swap function with the temp variable saves the values.

At first glance it looks like swap(&a[indice_pivot],&a[dx]); can fall into the same element. You can use assert( indice_pivot != dx ) to determine this (or, of course, put it in the swap function).

Answer 2

Swap (...)

• The enumerated integer overflow is undefined, which can occur with sufficiently large *x and *y .
• Absolutely no one can easily determine if swap() code is correctly implemented.

Partition (...)

• If i == j , your swap () function will not work correctly. This is because inside swap() we will have x == y , and your logic will not handle this case.