Velocity Reviews > C++ > array positioning question

# array positioning question

Guest
Posts: n/a

 02-20-2004
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[i] << 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,

/////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[i] << endl;
}

}

Dan Cernat
Guest
Posts: n/a

 02-20-2004

"Radhika Sambamurti" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) rg...
> 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[i] << 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,
>
> /////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[i] << endl;
> }
>
> }
>

after accessing memory past the array limit, anything can happen

Dan

Andrey Tarasevich
Guest
Posts: n/a

 02-20-2004
> ...
> 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.

--
Best regards,
Andrey Tarasevich

Guest
Posts: n/a

 02-20-2004
On Thu, 19 Feb 2004 18:36:19 -0800
Andrey Tarasevich <(E-Mail Removed)> wrote:

> > ...
> > 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.
>
> --
> Best regards,
> Andrey Tarasevich
>

Thanks for your great help. I at least understand what is happening now.

regards,

John Harrison
Guest
Posts: n/a

 02-20-2004

"Radhika Sambamurti" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) rg...
> 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[i] << 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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post tshad ASP .Net 6 06-07-2005 04:09 PM Leslie HTML 23 11-10-2003 09:26 AM Leslie HTML 4 11-02-2003 02:21 AM Pat Traynor HTML 3 09-24-2003 09:35 AM Matt Beckwith HTML 4 07-18-2003 10:47 PM