CODEWITHSUNDEEP
cquicksort
Dhruv Chandhok
Dhruv Chandhok

Reputation: 790

Swap using only two variables not working

I was writing a C code for quick sort but something went wrong. After some debugging i finally found where my code was going wrong. When i replaced

     {
a[lp]+=a[ub];
a[ub]=a[lp]-a[ub];
a[lp]=a[lp]-a[ub];
}

with 

  {
tmp=a[lp];
a[lp]=a[ub];
a[ub]=tmp;
}

my code started working. I am Curious to know why my initial implementation of swapping didn't work? Can anyone help me?

    #include<stdio.h>
    #define swap(a,b) (a)=(a)+(b);b=(a)-(b);(a)=(a)-(b);
    int a[]={7,1,5,2,3};
    int partition(int lb,int ub)
    {
    int k,hp,lp;
    k=a[ub];
    lp=lb-1;
    for(hp=lb;hp<ub;hp++)
    {
    if(a[hp]<k)
    {
    lp++;
    int tmp=a[lp];
    a[lp]=a[hp];
    a[hp]=tmp;
    }
    }
    lp++;
    a[lp]+=a[ub];
    a[ub]=a[lp]-a[ub];
    a[lp]=a[lp]-a[ub];
    return lp;
    }
    void quicksort(int lb,int ub)
    {
    if(lb<ub)
    {
    int pos=partition(lb,ub);
    quicksort(lb,pos-1);
    quicksort(pos+1,ub);
    }
    }
    int main()
    {
    quicksort(0,4); 
    int i;
    for(i=0;i<5;i++)printf("%d ",a[i]);
    printf("\n");
    return 0;
    }

Upvotes: 1

Views: 83

Answers (1)

harmic
harmic

Reputation: 30597

You need to consider what happens when lp == ub (ie. you are being asked to swap an element with itself).

Change it to this:

if (lp != ub) {
    a[lp]+=a[ub];
    a[ub]=a[lp]-a[ub];
    a[lp]=a[lp]-a[ub];
}

Example: http://ideone.com/AS1Dgf

Upvotes: 3

Related Questions