Strange things happen when swapping two vars in QuickSort

Question

I'm implementing QuickSort in C.

Here's my swap procedure:

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

And here's my Partition 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 swapping two variables, they magically (?) become 0. I did some debugging and everything seems working fine inside the swap procedure. But the array contains zeros at the end of some partitions (not all of them). The strange thing is that if I replace the swap procedure with

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

Everything works fine. Why?

Answer 1

Your swap function will not work if both pointers point to the same element. If they do 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 preserves the values.

At a glance it looks like swap(&a[indice_pivot],&a[dx]); could be hitting the same element. You can use assert( indice_pivot != dx ) to determine that( or of course put one in the swap function ).

Answer 2

Swap(...)

• Signed integer overflow is undefined which can occur with sufficiently large *x and *y.
• Absolutely nobody can easily tell if the code implementing swap() is correct.

Partition(...)

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