Search code examples
cquicksortswap

C: swapping by addition not working correctly but swapping by reference is?

I am trying to implement the quick sort algorithm in C, but I keep getting this weird error when I try to swap the elements x and y using the following snippet (which I intend to use in my code as a macro if I am able to fix this):

x = x + y; // step 1
y = x - y; // step 2
x = x - y; // step 3

#include <stdio.h>
#include <stdlib.h>
int partition (int *A, int p, int r) 
{
    int i, j, pivot;
    pivot = A[r];
    i = (p - 1);
    for (j = p; j < r; j++) {
        if (A[j] <= pivot) {
            i++;       
            printf ("Before: A[i] = %d, A[j] = %d\n", A[i], A[j]);
            A[i] = A[i] + A[j];
            printf ("A[i] = %d ", A[i]);
            A[j] = A[i] - A[j];
            printf ("A[j] = %d ", A[j]);
            A[i] = A[i] - A[j]; 
            printf ("A[i] = %d\n", A[i]);
            printf ("Finally: A[i] = %d, A[j] = %d\n\n", A[i], A[j]);
        }
    }
    putchar ('\n');
    printf ("Before: A[i + 1] = %d, A[r] = %d\n", A[i + 1], A[r]);
    A[i + 1] = A[i + 1] + A[r];
    printf ("A[i + 1] = %d ", A[i + 1]);
    A[r] = A[i + 1] - A[r];
    printf ("A[r] = %d ", A[r]);
    A[i + 1] = A[i + 1] - A[r];
    printf ("A[i + 1] = %d\n", A[i + 1]);
    printf ("Finally: A[i + 1] = %d, A[r] = %d\n\n", A[i + 1], A[r]);
    return (i + 1);
}

int my_qsort (int *A, int p, int r) 
{
    int q;
    if (p < r && A != NULL) {
        q = partition (A, p, r); 
        my_qsort (A, p, q - 1);  
        my_qsort (A, q + 1, r);  
        return 1;               
    } 
    return 0;
}

int display (int *arr, int len) 
{
    int i;
    if (len == 0) {
        printf ("Array is empty.\n");
        return 0;
    }
    for (i = 0; i < len; i++) {
        printf ("%d ", arr[i]);
    }
    putchar ('\n');
    return 1;
}

int main (int argc, char **argv) 
{
    int i, len = argc - 1;
    int arr[len];
    for (i = 0; i < len; i++) {
        arr[i] = atoi (argv[i + 1]);
    }
    puts ("Before quick sort:");
    display (arr, len);
    my_qsort (arr, 0, len-1);
    puts ("After quick sort:");
    display (arr, len);
    return 0;
}

I apologise if this was too long. I tried isolating the swapping problem into a minimum working example but it worked fine and did not exhibit the error. Also the ugly print statements are necessary to illustrate whats wrong. Here is part of the output when I run the program as:

./prg 9 8 7 6 5 4 3 2 1 | less

enter image description here

As you can see for A[i] = 8 and A[j] = 8, step 1 gives 16 (correct) but then step 2 and step 3 produce 0 ?? This is really weird given that the swapping is working correctly for the first swapping (marked with a tick). AS mentioned in the title, I tried it with the other swapping methods like using a temporary variable and by using a function swap() by passing pointers -- they all work. This is the only instance in which this is not working. I could be missing something very simple and that would be really embarrassing. Any ideas ?

Solution

  • If i + 1 is equal to r or i is equal to j then you will have

    printf ("Before: A[i + 1] = %d, A[r] = %d\n", A[i + 1], A[r]);

// Before: A{i + 1] = 8, A[r] = 8

A[i + 1] = A[i + 1] + A[r];
// A[i + 1] = 16, A[r] = 16

printf ("A[i + 1] = %d ", A[i + 1])
// A[i + 1] = 16

A[r] = A[i + 1] - A[r];
// A[r] = A[i + 1] = 0

printf ("A[r] = %d ", A[r]);
// A[r] = 0

A[i + 1] = A[i + 1] - A[r];
// A[i + 1] = A[r] = 0

printf ("A[i + 1] = %d\n", A[i + 1]);
// A[i + 1] = 0

printf ("Finally: A[i + 1] = %d, A[r] = %d\n\n", A[i + 1], A[r]);
// Finally: A[i + 1] = 0, A[r] = 0

    That is using your method of swapping you can not swap an object with itself.