So I wanted to create a bubble sort algorithm and I have it working properly, I was just wondering if anyone could take a look at my code and give me any advice/suggestions on making it more efficient or if I did anything I should avoid doing. I would really appreciate any tips! I know that typically the bubble sort algorithm shouldn't print out each pass thru or maybe it shouldn't display anything at all, but I just wanted to add those print statements for testing purposes and so that I could see that the algorithm was working properly
///////////////////////////////////
// //
// Bubble Sort Algorithm //
// --------------------- //
// //
// Bubble Sort Algorithm //
// using C++ //
// //
// Date: 5/12/16 //
// //
///////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
//==========================================================================================
template <typename T>
void displayList(std::vector<T> theList) {
if (theList.size() == 0)
std::cout << "*** Cannot display empty list ***\n\n";
else {
int counter = 1;
std::vector<T>::iterator listIter;
for (listIter = theList.begin(); listIter != theList.end(); listIter++) {
// checks if a comma should be placed after an item
if (listIter != theList.end()) {
if (counter == theList.size())
std::cout << *listIter << "\n";
else
std::cout << *listIter << ", ";
}
counter++;
}
}
}
//==========================================================================================
template <typename T>
void bubbleSort(std::vector<T> & theList) {
if (theList.size() == 0) {
std::cout << "BubbleSort Begin:\n"
<< "----------------------------\n"
<< "| *Error: List is empty\n"
<< "----------------------------\n\n";
}
else {
bool sorted = false;
bool altered_list;
int passthru_counter = 1;
int counter = 0;
std::vector<T>::iterator listIter;
std::cout << "Intial List Order: ";
displayList(theList);
std::cout << "\nBubbleSort Begin:\n-------------------------------------------------\n";
while (sorted == false) {
counter = 0;
altered_list = false;
for (listIter = theList.begin(); listIter != theList.end(); listIter++) {
// if the list was stepped thru and no items were out of place
if (counter + 1 < theList.size()) {
if (theList[counter] > theList[counter + 1]) {
T temp = theList[counter];
theList[counter] = theList[counter + 1];
theList[counter + 1] = temp;
altered_list = true;
std::cout << passthru_counter << " pass thru:\t";
displayList(theList);
passthru_counter++;
break;
}
else
counter++;
}
else {
if (altered_list == false) {
sorted = true;
break;
}
}
}
}
std::cout << "-------------------------------------------------\n";
std::cout << "*** The list is sorted\n";
std::cout << "*** # of pass thrus to sort = " << passthru_counter << "\n";
std::cout << "-------------------------------------------------\n\n";
}
}
//==========================================================================================
int main() {
std::vector<std::string> testList;
// test values
testList.push_back("lol");
testList.push_back("omg");
testList.push_back("wtf");
testList.push_back("kek");
testList.push_back("btw");
testList.push_back("fyi");
bubbleSort(testList);
system("PAUSE");
return 0;
}
Why use iterators as your for loop condition, and also employ a counter? You could just use a counter? That would allow you to avoid the constant if/else within the loop (since your end condition can be size - 1).
The alternative, would be to use two iterators (which may save some additional costs associated with the array element access - not in itself expensive - but since you are passing in a reference to a vector, some compilers may force an additional pointless load op on 'begin' for each element access). Again, you can engineer your loop to test the 'next' element is not equal to end.
[source]
if(theList.size() < 2) return;
auto end = theList.end();
bool altered_list = true;
while(altered_list)
{
altered_list = false;
I suppose the correct way to swap elements would be with std::swap, which would remove the 'temp' variable, and make the code a little clearer to read.
The pass through counter seems to be a little superfluous (unless it's just a formatting thing).
The 'sorted' flag serves no purpose. You already have 'altered_list', which gives you the same information.
It could take a const ref to the vector (rather than making a copy each time).
Again, that counter has returned!
If you want to see if the vector is empty, use the empty method! (size is typically implemented as a subtraction, so can be very modestly more expensive). Therefore repeatedly checking whether counter is equal to the size() is not considered good practice!
The if(iter != list.end()) check in the for loop is pointless. That condition is already checked by the for loop condition, so it can never enter the 'else'
Repeatedly doing if/else's for commas is probably a bad idea.
[source]
if(theList.empty()) {
// blah
}
else {
auto it = theList.begin();
auto end = theList.end();
cout << *it++;
for(; it != end; ++it)
cout << ", " << *it;
}
[/source]
Why use iterators as your for loop condition, and also employ a counter? You could just use a counter? That would allow you to avoid the constant if/else within the loop (since your end condition can be size - 1).
The alternative, would be to use two iterators (which may save some additional costs associated with the array element access - not in itself expensive - but since you are passing in a reference to a vector, some compilers may force an additional pointless load op on 'begin' for each element access). Again, you can engineer your loop to test the 'next' element is not equal to end.
[source]
if(theList.size() < 2) return;
auto end = theList.end();
bool altered_list = true;
while(altered_list)
{
altered_list = false;
I suppose the correct way to swap elements would be with std::swap, which would remove the 'temp' variable, and make the code a little clearer to read.
The pass through counter seems to be a little superfluous (unless it's just a formatting thing).
The 'sorted' flag serves no purpose. You already have 'altered_list', which gives you the same information.
Your display list function....
It could take a const ref to the vector (rather than making a copy each time).
Again, that counter has returned!
If you want to see if the vector is empty, use the empty method! (size is typically implemented as a subtraction, so can be very modestly more expensive). Therefore repeatedly checking whether counter is equal to the size() is not considered good practice!
The if(iter != list.end()) check in the for loop is pointless. That condition is already checked by the for loop condition, so it can never enter the 'else'
Repeatedly doing if/else's for commas is probably a bad idea.
[source]
if(theList.empty()) {
// blah
}
else {
auto it = theList.begin();
auto end = theList.end();
cout << *it++;
for(; it != end; ++it)
cout << ", " << *it;
}
[/source]
Thank you, I appreciate the help! :D I like your suggestions
