Jump to content
  • Advertisement
Sign in to follow this  
Shruubi

c++ bubble sort problem

This topic is 2615 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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;
}

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

for (i = 0; i <= elements; i++)
{
cout << list << 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
Advertisement

Hint:
For an array with N elements, only the 0th to the (N-1)th elements are accessible.


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

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


(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
so if i had an array of 5 elements, then i only have access to array[0] and not array[1] through array[5]?


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='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]?


(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;
}

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

for (i = 0; i <= elements; i++)
{
cout << list << 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

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


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 is an invalid element
On line 25: When i == elements, list and list[i+1] are invalid elements

Share this post


Link to post
Share on other sites

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


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 is an invalid element
On line 25: When i == elements, list 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
for (i = 0; i <= elements; i++) //get the individual numbers
this has to be
for (i = 0; i < elements; i++) //get the individual numbers


In your sort you made several mistakes.


temp= list [(i+1)];
list= list[i+1];
list=temp;

you delete list by writing list[i+1] in it.. twice.


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


here you swap the elements when they are not supposed to be swapped. if list 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.


//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;
}




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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!