Bubble sorting with c++

[Jack Van Stone]

Hi guys,
I am trying to bubble sort an array ascendingly, using bubble sort. However, it seems to work only when the size of the array is small (3 or 4 value), but, for instance, if I tried 8 different values, the program doesn't work. Please take a look at my program.
(The program takes the name and GPA of n numbers of students and sorts things ascendingly according to GPA)
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
int main ()
{
int n;
cout << "Enter number of students n bet 1 and 30: ";
cin >> n;
cout << endl;
while ( (n < 1) || (n>30) )
{
cout << "Invalid Input, Reenter: ";
cin >> n;
cout << endl;
}
float score[n], temp;
string name[n], stemp;
for (int k=0; k < n; k++)
{
cout << "Enter name of the student: ";
cin >> name[k];
cout << endl;
cout << "Enter his/her GPA: ";
cin >> score[k];
cout << endl;
while ( (score[k] > 4.0) || (score[k] < 0.0) )
{
cout << "Invalid GPA, Please Re-enter: ";
cin >> score[k];
cout << endl;
}
}
for ( int rn = 0; rn <= n-2 ; rn++)
{
for (int c = 1; c < n; c++)
{
if (score[rn] > score[c])
{
temp = score[rn] ;
stemp = name[rn];
score[rn] = score[c];
name [rn] = name[c];
score[c] = temp;
name[c] = stemp;
}
}
}
cout << "The New List: "<< endl;
for (int u =0; u<n ; u++)
cout << setw(10) << name[u] << setw(10) << score[u] << endl;
system("pause");
return 0;
}

[ne555]

that's not bubble sort
bubble sort compare adjacent elements.

seems more like selection sort.
it fails because you are searching the entire array for the smallest element, even the part that's already sorted.

[Jack Van Stone]

can you, please, help me?

[Uk Marine]

#include <iostream> 
#include <iomanip>
#include <string>

using namespace std;

int main()
{
	const int n = 10;
	float score[n], temp;
	string name[n], stemp;
	for (int k = 0; k < n; k++)
	{
		cout << "Enter name of the student: ";
		cin >> name[k];
		cout << endl;
		cout << "Enter his/her GPA: ";
		cin >> score[k];
		cout << endl;
		while ((score[k] > 4.0) || (score[k] < 0.0))
		{
			cout << "Invalid GPA, Please Re-enter: ";
			cin >> score[k];
			cout << endl;
		}
	}

	for (unsigned int i = 0; i < n - 1; ++i)
	{
		for (unsigned int j = 0; j < n - i - 1; ++j)
		{
			if (score[j] > score[j + 1])
			{
				float temp = score[j];
				stemp = name[j];

				score[j] = score[j + 1];
				score[j + 1] = temp;

				name[j] = name[j + 1];
				name[j + 1] = stemp;
			}
		}
	}

	cout << "The New List: " << endl;

	for (int u = 0; u<n; u++)
		cout << setw(10) << name[u] << setw(10) << score[u] << endl;

	system("pause");
	return 0;
}

Note that the bubble sort algorithm isn't the best for performance as it results in a O(n^2) time complexity. Best case scenario is O(n) but that's only when your array is already sorted.

[Jack Van Stone]

Thank you so much
Unfortunately, I am new to C++, and, as part of the CS course, I need to do bubble sorting.
Can I please know why are we using this part?
for (unsigned int i = 0; i < n - 1; ++i)
{
for (unsigned int j = 0; j < n - i - 1; ++j)
{
if (score[j] > score[j + 1])
{
float temp = score[j];
stemp = name[j];

score[j] = score[j + 1];
score[j + 1] = temp;

name[j] = name[j + 1];
name[j + 1] = stemp;
}
}
}
For instance we stated that temp is float in the beginning, then why are we stating it as float again. Also, we are intializing (i) and not using it.
I'm sorry if my questions are inane or something; I am new to C++, particularly with only 3 months of knowledge.
Thank you so much for your effort

[ne555]

> For instance we stated that temp is float in the beginning, then why are we stating it as float again.
those are two different variables, they have the same name, but their scope is different.

float temp; //to distinguish, let's call this `temp1'
for(...)
   for(...)
      if(...){
         float temp; //and this one `temp2'
      }

temp2 only exists inside the `if', temp1 may be seen in all main.
now, given the purpose of `temp' there is no advantage for it to live outside the conditional. You should limit the scope of your variables so i suggest you to remove the declaration at line 10.
the same may be said about `stemp', you should declare it inside the if.

> Also, we are intializing (i) and not using it.
it is used as the stop limit of the second loop

for (unsigned int i = 0; i < n - 1; ++i)
   for (unsigned int j = 0; j < n - i - 1 /*here*/; ++j) 

first you'll traverse the whole array (i=0)
then you leave out the last element (i=1)
you will be leaving out the elements to the right, that the algorithm already sorted
at the end you only check two elements (i=n-2, so j is 0 and you check 0 and 1)

[Jack Van Stone]

Thank you

[punksheep]

Hi Jack Van Stone,
Bubble sort is a double loop comparing two adjacent elements each time... if there are not in order, you swap them.

To swap, use std::swap instead, it's a lot better :

#include <algorithm>
...
	std::swap(a,b);

You can swap any variable a, b, both the same type.
And it gets very readable.

In the example here, you can :

	std::swap(score[j], score[j+1]);
	std::swap(name[j], name[j + 1]);