0

In the following code (for bubble sort), the variable origN was not referenced at all after its declaration, but at the end of the program, the value of origN is output as 1 (instead of 4):

int main(){
    int arr[] = {3,4,2,1};
    int origN = 4;
    int n = 4;
    while(true)
    {
        bool swapped = false;
        for(int i = 0; i<n; ++i)
        {
            if(arr[i] < arr[i-1])
            {
                swap(arr[i],arr[i-1]);
                swapped = true;
            }
        }
        n -= 1;
        if(!swapped)
            break;
    }
    cout<<"origN="<<origN<<endl;
    return 0;
}

But if I use the variable n as a pointer:

int *n = new int(4);

the value of origN remains unchanged, and is correctly output as 4!

Why is the value of origN changing along with the value of n?

jatinderjit
  • 1,359
  • 8
  • 21

2 Answers2

4

Within the for loop you are reading and writing an element outside of the array. It is undefined behavior. Could be that it changes origN

for(int i = 0; i<n; ++i)
{
    if(arr[i] < arr[i-1]) // <-- `i-1` can be -1
    {
        swap(arr[i],arr[i-1]); // <--
        swapped = true;
    }
}

You can try to start the loop from 1:

for(int i = 1; i<n; ++i)
AlexD
  • 32,156
  • 3
  • 71
  • 65
0

The basic problem is that you are actually underflowing on the arr array.

When n becomes 0, you will do a swap(arr[i],arr[i-1]); where i == 0.

Both arr and originN are allocated in your example on the stack and are near eachother. The underflow results in overwriting the value of the originN.

This does not happen if you allocate the array on the heap although you still keep underflowing (and overwriting the memory at the heap location &arr[-1].

ds27680
  • 1,993
  • 10
  • 11