Sign in to follow this  
Shruubi

c++ bubble sort problem

Recommended Posts

So, as a little excercise for myself, i'm writing a bubble sort program in c++ which allows you to have a user-specified amount of numbers to be sorted.

my problem is that when i run the actual sorting portion of my program, with 3 numbers entered (3, 1 and 2 respectively) it sorts 1 and 2 into it's respective spots and the third number is some huge number. above 3 numbers, it doesn't correctly sort the numbers.

[source lang="cpp"]

#include <iostream>

using namespace std;

int main()
{
int elements;
int temp;
int i;

cout << "enter how many numbers need to be sorted (0 indexed, 2 means 3 numbers will be sorted etc): ";
cin >> elements;

int list[elements];

for (i = 0; i <= elements; i++) //get the individual numbers
{
cout << "enter a number: ";
cin >> list[i];
}

//begin bubble sort
for (i = 0; i <= elements; i++) //sorting here
{
if (list[i] > list[(i+1)]) //if number being compared is greater than the next number in list
{
temp = list[(i+1)];
list[i] = list[i+1];
list[i] = temp;
}
else if (list[i] < list[(i+1)])
{
temp = list[i];
list[(i)] = list[(i+1)];
list[(i+1)] = temp;
}
}

for (i = 0; i <= elements; i++)
{
cout << list[i] << endl;
}

cin.get();
return 0;
}
[/source]

if anyone can see my error (as i am sure it is one huge blaring error i just can't see), could they please point me in the direction of fixing it?

Thanks

Share this post


Link to post
Share on other sites
[quote name='fastcall22' timestamp='1306037044' post='4814105']
Hint:
For an array with N elements, only the 0th to the (N-1)th elements are accessible.
[/quote]

so if i had an array of 5 elements, then i only have access to array[0] and not array[1] through array[5]?

if so, then how do i access the other elements?

Share this post


Link to post
Share on other sites
[quote name='Shruubi' timestamp='1306037482' post='4814108']
so if i had an array of 5 elements, then i only have access to array[0] and not array[1] through array[5]?
[/quote]

(Bad wording on my part, sorry.)
Not quite; if you have an array of 5 elements, int array[5], then to access those elements, you use array[0], array[1], array[2], array[3], and array[4] -- exactly five elements. Be sure your looping constructs do not violate the bounds of your array, meaning, if you want to iterate over all of the elements of the array, be sure that "i" ranges from 0 to 4. Be sure that "i+1" is also within the boundaries of the array. Reading and writing outside of the array is undefined, and at best, will give you garbage numbers, or at worst, your program can behave correctly.

In addition, you don't seem to have the bubble sort down quite yet. The bubble sort swaps neighboring elements if the "left neighbor" should be ordered after the "right neighbor," and does so repeatedly until the entire array is sorted. The code you have only performs only one iteration, swapping neighbors if they're not equal. (There's a subtle bug in the swapping code on lines 27-29; but should you really be swapping neighbors here?)

Share this post


Link to post
Share on other sites
Hidden
[quote name='Shruubi' timestamp='1306037482' post='4814108']so if i had an array of 5 elements, then i only have access to array[0] and not array[1] through array[5]?[/quote]

That's not what was said: if you have N elements, then the indices run from 0 to (N-1). That is to say that you'd have array[0], array[1], array[2], array[3] and array[4]. array[5] doesn't exist. Accessing it is, unfortunately, an error that the compiler will not detect for you.

Share this post


Link to post
[quote name='fastcall22' timestamp='1306037846' post='4814110']
[quote name='Shruubi' timestamp='1306037482' post='4814108']
so if i had an array of 5 elements, then i only have access to array[0] and not array[1] through array[5]?
[/quote]

(Bad wording on my part, sorry.)
Not quite; if you have an array of 5 elements, int array[5], then to access those elements, you use array[0], array[1], array[2], array[3], and array[4] -- exactly five elements.
[/quote]

ok, sorry, i'm a little confused now, what is my error?

Share this post


Link to post
Share on other sites
Hidden
well, i thought i'd fixed it, it now correctly sorts some given sets, however some sets (for example 3, 1, 7, 10) etc do no correctly sort properly.

[source lang="cpp"]
#include <iostream>

using namespace std;

int main()
{
int elements;
int temp;
int i;

cout << "enter how many numbers need to be sorted (0 indexed, 2 means 3 numbers will be sorted etc): ";
cin >> elements;

int list[elements];

for (i = 0; i <= elements; i++) //get the individual numbers
{
cout << "enter a number: ";
cin >> list[i];
}

//begin bubble sort
for (i = 0; i < elements; i++) //sorting here
{
if (list[i] > list[(i+1)]) //if number being compared is greater than the next number in list
{
temp = list[(i+1)];
list[(i+1)] = list[i];
list[i] = temp;
}
else if (list[i] < list[(i+1)])
{
temp = list[i];
list[(i)] = list[(i+1)];
list[(i+1)] = temp;
}
}

for (i = 0; i <= elements; i++)
{
cout << list[i] << endl;
}

cin.get();
return 0;
}
[/source]

by making it run the 'for' loop with the conditions (i = 0; i <= elements; i++) when the program checks for list[(i+1)] it is looking for a number that doesn't exist. so i changed it to for (i = 0; i < elements; i++).

thank you. also, anyone else who see's this, feel free to look into optimizing the code.

Share this post


Link to post
[quote name='Shruubi' timestamp='1306038108' post='4814114']
ok, sorry, i'm a little confused now, what is my error?
[/quote]

On line 11: 2 means 2 numbers will be sorted, 3 means 3 numbers will be sorted, etc
On line 19: When i == elements, list[i] is an invalid element
On line 25: When i == elements, list[i] and list[i+1] are invalid elements

Share this post


Link to post
Share on other sites
[quote name='fastcall22' timestamp='1306039136' post='4814118']
[quote name='Shruubi' timestamp='1306038108' post='4814114']
ok, sorry, i'm a little confused now, what is my error?
[/quote]

On line 11: 2 means 2 numbers will be sorted, 3 means 3 numbers will be sorted, etc
On line 19: When i == elements, list[i] is an invalid element
On line 25: When i == elements, list[i] and list[i+1] are invalid elements
[/quote]

ok then, thank you for your help. :)

Share this post


Link to post
Share on other sites
[code]for (i = 0; i <= elements; i++) //get the individual numbers[/code]
this has to be
[code]for (i = 0; i < elements; i++) //get the individual numbers[/code]


In your sort you made several mistakes.

[code]
temp= list [(i+1)];
list[i]= list[i+1];
list[i]=temp;
[/code]
you delete list[i] by writing list[i+1] in it.. twice.


[code]else if (list[i] < list[(i+1)]){
temp= list[i];
list[i] = list(i+1)];
list[(i+1)] = temp;
}
[/code]

here you swap the elements when they are not supposed to be swapped. if list[i] is smaller than list[i+1] then there is nothing to do.

The main problem is that a bubble sort uses two for statements. if you would fix the problems above, your programm would not do what you want. It should look like that.
Did not check the bounds exactly but this should give you a hint about how it works.

[code]
//sort
for(int i=0; i<(elements-1);i++)
for(int j=0; j<(elements-(1+i));j++)
if(list[j] > list[j+1]){
int temp=list[j];
list[j]= list[j+1];
list[j+1]=temp;
}


[/code]

i wonder why your posted code even gets to the sort. It is supposed to get an access violation oder index out of bounds exeption.

Share this post


Link to post
Share on other sites
In C++, accessing outside the bounds of a regular array is undefined behavior, which means exactly what it says: there's no guaranteed behavior of any sort. It's not guaranteed to throw an exception, cause an access violation or give any diagnostic at all.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this