2

When I use following code for swapping in quick-sort it is working.

void s(int *a, int *b)
{
   int t = *a;
   *a = *b;
   *b = t;
}

But when I use following code to swap elements for quick-sort, it is not working.

void s(int *a, int *b)
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

I can't figure out what is wrong with the code.

I am adding my quick-sort code below for clarification.

void  qs(int *a, int l, int h){
   if( l<h){
      int pi = pa(a, l, h);
      qs(a, l, pi-1); qs(a, pi+1, h);       
   }
}
int pa(int *a, int l, int h){
    int p = a[h], lt = l-1, i;
    for(i=l; i<=h-1; i++) if(a[i]<=p) s(&a[++lt], &a[i]);         
    s(&a[lt+1], &a[h]);
    return lt+1;        
}
Improve this question
4
  • You should really explain better than "it is not working". What input did you give it? What steps have you taken to investigate? Commented Feb 25, 2014 at 5:00
  • 1
    Why on earth use such an obscure, non-obvious technique? You're just exchanging values. Being clever about it earns you no points. Commented Feb 25, 2014 at 5:04
  • 1
    Computer memory is very cheap. Why make life difficult? Just leads to errors when you start getting into that mindset. (as demonstrated by this question) - An aside use braces and start learning to count from zero Commented Feb 25, 2014 at 5:18
  • 3
    Why do you think 3 assignments plus 3 arithmetic operations will be faster than 3 assignments plus 0 arithmetic operations? For the cost of one int of local variable (which might be placed in a register anyway), you are paying a penalty in performance and clarity of code. You would do far better to use the simple swap code with a temporary variable than any messing around with additions and subtractions. If you want to speed the swap up, make it into static inline void swap(int *a, int *b) and let the compiler optimize. Commented Feb 25, 2014 at 6:16

6 Answers 6

Reset to default
2

While doing a quick sort, in the partition method call, you would be calling the swap on the same position sometimes. So, this line in the swap method:

*a = *a + *b;

would mean that both *a and *b now have (*a + *b) as its the same position that the change is getting reflected in. Better to have a check of a!=b before you swap.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Got this issue lol, such a funny bug that you are like 0_0 :)
1 
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;

That code is a classic trick for swapping numbers that does work. The issue has to be in what values are being passed in. You need to verify that the pointers you are working with are not the same and that you are not having an issue with overflow.

Improve this answer

1 Comment

Exactly what jxh said.
1

the swapping is correct, probably you have a bug in your overall quicksort. or compiler optimizes something

Improve this answer

Comments

1

There are two problems with the second function. One, Yu Hao had identified, but has since removed, is that you have the potential for signed integer overflow.

Assuming you are only dealing with numbers that do not cause overflow, the second problem is that if the two pointers point to the same object, the object will end up with the value of 0, regardless of what value it started with.

Suppose you have variable c initialized to 17, and you call swap with swap(&c, &c):

   .-----------.
  \|/          |
+--'----+    +---+    +---+
| c: 17 |    | a |    | b |
+--.----+    +---+    +---+
  /|\                   |
   `--------------------'

Since inside swap(), both a and b point to c, the result of the last assignment will put the value 0 into c, because *a = *a - *b would be equivalent to c = c - c.

To fix the overflow issue, you can make sure the sum never overflows by making sure the arguments have opposite signs. To fix the "point to same object" issue, just check of that inside the swap function.

void swap (int *a, int *b) {
    /*...as you had it...*/
}

void s (int *a, int *b) {
    if (a != b) {                /* not same object */
        if (*a > 0 != *b > 0) {
            swap(a, b);          /* not same sign */
        } else {
            *a = -*a;
            swap(a, b);
            *b = -*b;
        }
    }
}

As you can see, this is already considerably more complicated than employing the first version of your swap function. If you are worried that using another variable might make the program deficient in some way, put those fears aside. Nearly all compilers used for commercial development will recognize a swap, and generate the optimal code for it.

Improve this answer

1 Comment

Indeed, it's more likely that the problem is in how he uses swap() in his quicksort program, that's why I removed my answer :)
0

This code works for me.

#include <stdio.h>
void swap(int*, int*);  
int main()
{
   int x, y;
   printf("Enter the value of x and y\n");
   scanf("%d%d",&x,&y);
   printf("Before Swapping\nx = %d\ny = %d\n", x, y);
   swap(&x, &y); 
   printf("After Swapping\nx = %d\ny = %d\n", x, y); 
   return 0;
}

void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}

tried it on, http://www.compileonline.com/compile_c_online.php

So, my point is the swapping is correct and I think you have a problem with your quick sort code.

Improve this answer

6 Comments

This is the same code he has up there. This doesn't solve his/her issue.
I've already flagged his question, actually I've put this up to make a point that the code works fine, and the mistake is on his implementation side.
incase you want to verify my statement, please implement it on the link given above. The swapping works fine.
Obviously it works, but that's not the OP's issue. The issue is why that swap doesn't work with his quick sort, but the other one does (using temp).
Then he should post his quick sort. because, the fault isn't within this one.
|
0

I would use the first way to swap values.

The second one appears as though it should work. but is limited in scope and is not as good:

  1. if both *a and *b point to the same value you get 0 as the value
  2. you can overflow with large values
  3. it is not as efficient, using 3 assignment and 3 addition operations

It should work, unless your compiler is optimizing something for you, or you are running into case 1 or 2 above... for example: a = 2 b = 3

*a = *a + *b; // *a = 2 + 3 = 5
*b = *a - *b; // *b = 5 - 3 = 2
*a = *a - *b; // *a = 5 - 2 = 3
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.