0

The algorithm to swap the values of two integers x and y without using a tmp variable is 

x = x + y;
y = x - y;
x = x - y;

I've written a code to sort an array by passing it to a method. The method accepts the array in a pointer *ptr. Thus, the elements of the array, arr[0], arr[1],... would be accessed with the pointer variable as *(ptr + 0), *(ptr + 1),.... However, the problem I'm facing is that when I try to swap the values of the array while sorting by referencing the memory location with a pointer, without the use of a temporary variable, the array is not getting sorted the way I expect and, instead, I see some random elements getting inserted into the array.

This is my array sorting code (selection sort - the sort algorithm is correct): 

void sort(int *arr, int n){
    int i,j,m;
    for(i=0; i<n-1; i++){
        m = i;
        for(j=i+1; j<n; j++){
            if(arr[j] < arr[m])
                m = j;
        }
        //swapping arr[i] and arr[m]
        *(arr + i) = *(arr + i) + *(arr + m);
        *(arr + m) = *(arr + i) - *(arr + m);
        *(arr + i) = *(arr + i) - *(arr + m);
    }
    //print the array...
}

void main(){
    int arr[] = {2,4,3,5,8,7};
    sort(arr, 6);
}

INPUT: 

2 4 3 5 8 7

EXPECTED OUTPUT: 

2 3 4 5 7 8

OBTAINED OUTPUT: 

0 3 0 0 7 8

Why is this happening? What am I doing wrong?

progyammer
  • 1,498
  • 3
  • 17
  • 29
  • How do you call the function? Where is your [Minimal, Complete, and Verifiable Example](http://stackoverflow.com/help/mcve)? – Some programmer dude Sep 12 '17 at 16:05
  • @Someprogrammerdude I've added the main method and shown how I call the sort method – progyammer Sep 12 '17 at 16:08
  • 1
    Why are you trying to swap without using a temporary? This is kind of like trying to drive nails without using a hammer -- you can do it if you really want to, but simply using a hammer (or, in this case, a temporary variable) is far, far easier, and almost invariably better. – Steve Summit Sep 12 '17 at 16:15
  • @SteveSummit Honestly, just trying out random stuff; exploring C. – progyammer Sep 12 '17 at 16:18
  • Although unlikely, the `x = x + y` code can theoretically overflow. See https://stackoverflow.com/questions/44344453/is-this-way-is-prefered-to-swap-two-variable-without-temp-in-c , – Steve Summit Sep 12 '17 at 16:27
  • @SteveSummit I've had the overflow thing in mind but then it doesn't really cause a problem while dealing with signed numbers. I tried with `x = 32767; y = 1` and also `x = -32768; y = -12`. It worked. But in the case of unsigned numbers, I'd definitely use a temp variable because people have said on the question you linked that discarding a temp variable gives no significant memory advantage. – progyammer Sep 12 '17 at 16:44
  • 1
    @progyammer As it happens, it'll always work on unsigned numbers, where "wraparound" behavior on over/underfllow is guaranteed bu the C Standard. Strictly speaking, that wraparound behavior is *not* guaranteed for signed numbers (although it does typically work as you expect on the vast majority of machines). – Steve Summit Sep 12 '17 at 17:00

1 Answers1

5

The algorithm to swap the values of two integers x and y without using a tmp variable is

x = x + y;
y = x - y;
x = x - y;

One of several problems with this approach is that it does not work when x and y expressions refer to the same memory location. This is exactly what happens when an item is in its place after completion of the nested loop, i.e. when i is the same as m.

Adding if (i == m) continue before going into the swap will fix this problem.

Demo.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523