• Advertisement
Sign in to follow this  

Bubble Sort Algorithm Review

This topic is 710 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

Hello!

 

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;
}
Edited by NUCLEAR RABBIT

Share this post


Link to post
Share on other sites
Advertisement
Your for loop seems a bit rubbish :)

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;

auto it = theList.begin();
auto next = it + 1;

for(; next != end; ++it, ++next) {
if(*it > *next) {
std::swap(*it, *next);
altered_list = true;
}
}
}
[/source]

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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

Your for loop seems a bit rubbish :)

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;

auto it = theList.begin();
auto next = it + 1;

for(; next != end; ++it, ++next) {
if(*it > *next) {
std::swap(*it, *next);
altered_list = true;
}
}
}
[/source]

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement