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
c++ bubble sort problem
Author
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?
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?)
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.
Author
[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?
Author
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.
[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.
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
Author
[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.
for (i = 0; i <= elements; i++) //get the individual numbersthis has to be
for (i = 0; i < elements; i++) //get the individual numbersIn 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
