array positioning question

[Radhika Sambamurti]

Hi,
I'm a relative newbie....

I've written a program to do a bubble sort. take in numbers and sort them.
My question is: at the very end of the sort() function, when I have to output the result to stdout, the only code that does this correctly is as follows:
//output of sorted array

for(i=1; i<n+1; i++)
{
cout << "value of i is: " << num_array << endl;
}

}

When i tried saying - for(i=0; i<n; i++),
the zero'th element was some hex garbage (being the address of the array i assume) and only sub[1,2,3,4] were output. So why does num_array[0] give me hex? I used gdb to debug this, but this just verifies my findings. I would like to know why.

Thank you,
Radhika

/////Code below//////////////////////////

//Sorting in ascending
#include <iostream>
using namespace std;

const int SIZE= 5;
void sort(int number[], const int SIZE); //prototype never takes array size
int main()
{
int number[SIZE] = {49,19,23,69,7};

sort(number, SIZE); //Function call with array
//always only array name
return 0;
}

///////// Function sort()

void sort(int num_array[SIZE], const int n)
{
int temp, i;

for(int k=0; k<n; k++) // outer loop
{
for(int j=0; j<n; j++) //inner loop
{
if(num_array[j] > num_array[j+1])
{
temp = num_array[j];
num_array[j] =num_array[j + 1];
num_array[j + 1] = temp;
//swapping the variables to make
//into ascending order

}
}
}

//output of sorted array

for(i=1; i<n+1; i++)
{
cout << "value of i is: " << num_array << endl;
}

}

 

[Dan Cernat]

Hi,
I'm a relative newbie....

I've written a program to do a bubble sort. take in numbers and sort them.
My question is: at the very end of the sort() function, when I have to

output the result to stdout, the only code that does this correctly is as
follows:

//output of sorted array

for(i=1; i<n+1; i++)
{
cout << "value of i is: " << num_array << endl;
}

}

When i tried saying - for(i=0; i<n; i++),
the zero'th element was some hex garbage (being the address of the array i

assume) and only sub[1,2,3,4] were output. So why does num_array[0] give me
hex? I used gdb to debug this, but this just verifies my findings. I would
like to know why.

Thank you,
Radhika

/////Code below//////////////////////////

//Sorting in ascending
#include <iostream>
using namespace std;

const int SIZE= 5;
void sort(int number[], const int SIZE); //prototype never takes array size
int main()
{
int number[SIZE] = {49,19,23,69,7};

sort(number, SIZE); //Function call with array
//always only array name
return 0;
}

///////// Function sort()

void sort(int num_array[SIZE], const int n)
{
int temp, i;

for(int k=0; k<n; k++) // outer loop
{
for(int j=0; j<n; j++) //inner loop
{

// didn't analize it too much, but
// when j == n-1 then j + 1 below is 1 past the end of array
// see what you can do about it
// then see if the problem persists

if(num_array[j] > num_array[j+1])
{
temp = num_array[j];
num_array[j] =num_array[j + 1];
num_array[j + 1] = temp;
//swapping the variables to make
//into ascending order

}
}
}

//output of sorted array

for(i=1; i<n+1; i++)
{
cout << "value of i is: " << num_array << endl;
}

}

after accessing memory past the array limit, anything can happen

Dan

 

[Andrey Tarasevich]

...
When i tried saying - for(i=0; i<n; i++),
the zero'th element was some hex garbage (being the address of the array i assume) and only sub[1,2,3,4] were output. So why does num_array[0] give me hex? I used gdb to debug this, but this just verifies my findings. I would like to know why.
...

In my experiments I get expected results from your program when I use
the 'for(i=0; i<n; i++)' version. However, your program produces
undefined behavior, which means that there is no way to predict anything.

The inner cycle in your 'sort' function iterates through all values of
'j' from '0' to 'n-1'. However, inside the cycle you access value of
'num_array[j+1]'. At the last iteration, when 'j' is equal to 'n-1', the
code will try to access 'num_array[n]', which is clearly a range error.

In practice this might or might not crash you program. If it doesn't
crash, it will drag into the mix an additional nonexistent element of
the array and try to process it together with the existing elements. The
result depends on the value of 'num_array[n]'. If it is smaller than the
smallest element of the array, it will eventually move to the beginning
of the array, which means that the original elements will reside in
1...n locations (that's what happened in your experiment). In my case
the original value of 'num_array[n]' was huge, which caused it to stay
at the end and consequently resulted in original elements residing in
0...n-1 locations (as if everything is working correctly).

I don't know how you managed to get _hex_ garbage. But with undefined
behavior it should not surprise anyone.

Correct the above error and use the 'for(i=0; i<n; i++)' version of the
cycle to print results. It should work fine.

 

[Radhika Sambamurti]

...
When i tried saying - for(i=0; i<n; i++),
the zero'th element was some hex garbage (being the address of the array i assume) and only sub[1,2,3,4] were output. So why does num_array[0] give me hex? I used gdb to debug this, but this just verifies my findings. I would like to know why.
...

In my experiments I get expected results from your program when I use
the 'for(i=0; i<n; i++)' version. However, your program produces
undefined behavior, which means that there is no way to predict anything.

The inner cycle in your 'sort' function iterates through all values of
'j' from '0' to 'n-1'. However, inside the cycle you access value of
'num_array[j+1]'. At the last iteration, when 'j' is equal to 'n-1', the
code will try to access 'num_array[n]', which is clearly a range error.

In practice this might or might not crash you program. If it doesn't
crash, it will drag into the mix an additional nonexistent element of
the array and try to process it together with the existing elements. The
result depends on the value of 'num_array[n]'. If it is smaller than the
smallest element of the array, it will eventually move to the beginning
of the array, which means that the original elements will reside in
1...n locations (that's what happened in your experiment). In my case
the original value of 'num_array[n]' was huge, which caused it to stay
at the end and consequently resulted in original elements residing in
0...n-1 locations (as if everything is working correctly).

I don't know how you managed to get _hex_ garbage. But with undefined
behavior it should not surprise anyone.

Correct the above error and use the 'for(i=0; i<n; i++)' version of the
cycle to print results. It should work fine.

Thanks for your great help. I at least understand what is happening now.
Your explanation was v helpful.

regards,
radhika

 

[John Harrison]

Hi,
I'm a relative newbie....

I've written a program to do a bubble sort. take in numbers and sort them.
My question is: at the very end of the sort() function, when I have to

output the result to stdout, the only code that does this correctly is as
follows:

//output of sorted array

for(i=1; i<n+1; i++)
{
cout << "value of i is: " << num_array << endl;
}

}

When i tried saying - for(i=0; i<n; i++),
the zero'th element was some hex garbage (being the address of the array i

assume) and only sub[1,2,3,4] were output. So why does num_array[0] give me
hex? I used gdb to debug this, but this just verifies my findings. I would
like to know why.
It's because your sort code is bugged.

[snip]

for(int k=0; k<n; k++) // outer loop
{
for(int j=0; j<n; j++) //inner loop
{
if(num_array[j] > num_array[j+1])

When j equals n - 1, j +1 equals n, which is past the end of the array. Fix
this problem and the other will go away

john