CODEWITHSUNDEEP
csortingdata-structuresquicksortswap
godeater
godeater

Reputation: 13

swapping without using 3rd(temporary variable) is giving diff answer in this program can someone tell me why?

when the swapping part is done with the help of 3rd variable(temporary variable) it works fine but when it is done without using temp variable(like a=a+b; b=a-b; a=a-b;)the output changes

this quick_sort program works fine but output is changing when method of swapping changes

#include<stdio.h>
void swap(int *a,int *b){/*
*a=*a+*b;
  *b=*a-*b;
  *a=*a-*b;*/
 int t=*a;
  *a=*b;
  *b=t;
}
int sort(int a[],int st,int piv){
int i=st-1,j,t;
for(j=st;j<=piv-1;j++){
if(a[j]<=a[piv]){
        i++;
   swap(&a[j],&a[i]);

  
}}
swap(&a[i+1],&a[piv]);
return i+1;

}
void quick(int a[],int st,int en){
if(st<en){
    int x=sort(a,st,en);
    quick(a,st,x-1);
    quick(a,x+1,st);
}
}
void main(){
int a[]={11,1,23,22,10,18,0,13},i;
quick(a,0,7);
for(i=0;i<8;i++)
printf("%d ",a[i]);

}

Upvotes: 0

Views: 51

Answers (1)

Χρήστος Χατζηπέτρος
Χρήστος Χατζηπέτρος

Reputation: 91

Let's take a look at your alternative version of swap!

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

Suppose a=x,b=y, then we get: a=x+y, followed by b=x+y-y=x and a=x+y-x=y. Those can prove that your code for swapping makes sense. But where's the catch? Your reasoning implies that int* a is independent of int* b. If you try calling swap(&a[0],&a[0]) while your expected behaviour is for a[0] to remain unchanged this doesn't happen due to a and b pointing to the exact same memory location.

Here's a correct version of it:

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

Edit: while this method will work for most cases, it can fail due to overflow of a+b. Do not use it in actual code, but feel free to keep it in order to understand the reason for if(a==b) return;.

Upvotes: 4

Related Questions