0

hi everyone this is my code below

#include <iostream>

using namespace std;

void printArray(int arr[],int size){
    cout<<"[ ";
    for(int i = 0;i<size;++i){
        cout<<arr[i]<<", ";
    }
    cout<<"\b\b ]\n";
}

void swap(int &a,int &b){
    a^=b^=a^=b;
}

void bubbleSort(int arr[],int n){
    for(int i = 0;i<n-1;++i){
        bool isSwap = false;
        for(int j = 0;j<n-1-i;++j){
            if(arr[j]>arr[j+1]){
                isSwap = true;
                swap(arr[j],arr[j+1]);
            }
        }
        if(!isSwap)
            break;
    }
}

int partition(int arr[],int l,int r){
    int i = l-1;
    int pivot = arr[r];
    for(int j = l;j<r;++j){
        if(arr[j]<pivot){
            ++i;
            swap(arr[j],arr[i]);
        }
    }
    swap(arr[r],arr[++i]);
    return i;
}

void quickSort(int arr[],int l,int r){
    if(l<r){
        int pivot_index = partition(arr,l,r);
        quickSort(arr,l,pivot_index-1);
        quickSort(arr,pivot_index+1,r);
    }
}


int main(){
    int a[] = {2,4,6,7,8,9,2,3,4,1,9,2,1,6,2,3,22};
    int size = sizeof(a)/sizeof(a[0]);
    printArray(a,size);
    quickSort(a,0,size-1);
    printArray(a,size);
    return(0);
}

I was practicing comparison based sorting algorithms in the above code. bubbleSort works fine but quickSort algorithm gives wrong result.

I usually compile my code using g++ compiler but sometime I also use clang++ For better code warning and suggestion.

When I compiled above code with clang++ it gave this warning

1.cpp:14:9: warning: unsequenced modification and access to 'a' [-Wunsequenced]
        a^=b^=a^=b;
         ~~    ^
1 warning generated.

So there is a problem with the swap algorithm but my swap algorithm logic is correct. I used the same swap in bubbleSort and this worked with this. algorithms(bubbleSort).

But it's not working with quickSort logic.

I just want to know why it's not working with quick sort.

Aadil Mughal
  • 19
  • 3
  • Why do you think the warning (and thus the swap code) is the cause of quicksort not working? – Thomas Feb 12 '22 at 18:28
  • you get exactly same warning by calling `bubbleSort` https://godbolt.org/z/99zv8z9rW – 463035818_is_not_an_ai Feb 12 '22 at 18:29
  • 1
    The behaviour you highlight is undefined before C++17; but, I believe, it is fully sequenced according the C++17 (and later) Standards. – Adrian Mole Feb 12 '22 at 18:30
  • 2
    why are you writing your own `swap` anyhow? Doing that in combination with `using namespace std;` is recipe for confusion and desaster. – 463035818_is_not_an_ai Feb 12 '22 at 18:30
  • [This answer](https://stackoverflow.com/a/47753609/10871073) explains assignment sequencing in C++11 and C++17. Presumably, it is also relevant for compound assignments. – Adrian Mole Feb 12 '22 at 18:32
  • The `a^=b^=a^=b` is unsequenced, so will result in **undefined behavior**. `std::swap` already is available, and will do the swap correctly (and in this case, more efficiently). But if you insist of using XOR, you'll want `a^=b; b^=a; a^=b;` – Eljay Feb 12 '22 at 18:32
  • fwiw, no warning with c++17: https://godbolt.org/z/f4hWf14G6. You better change your attitiude "So there is a problem with the swap algorithm but my swap algorithm logic is correct." it cannot be correct and wrong at the same time. 99.99% of all casese the compiler is right – 463035818_is_not_an_ai Feb 12 '22 at 18:33
  • 1
    wrong code can produce right results. sometimes, when you are lucky (or unlucky). That doesnt make it less wrong – 463035818_is_not_an_ai Feb 12 '22 at 18:34
  • 1
    @Eljay Even with `void swap(int& a, int& b){a^=b; b^=a; a^=b;}`, the result is still wrong if `a` and `b` refer to the same variable, in which case it is equivalent to `a=b=0;`. – prapin Feb 12 '22 at 19:02
  • @prapin void swap(int &a,int &b){ if(a!=b) {a^=b^=a^=b;} } – Aadil Mughal Feb 12 '22 at 19:13
  • @prapin • Agreed, due to the non-aliasing assumption. The result would be undefined behavior, which may be 0, but may be something else. – Eljay Feb 12 '22 at 19:27

0 Answers0