🔒 Locked

Bubble Sort Algorithm Review

Started by NUCLEAR RABBIT May 12, 2016 at 7:28 PM 2 replies 3.2k views

Original Post

May 12, 2016 at 7:28 PM

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

RobTheBloke

May 13, 2016 at 1:36 AM

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.

RobTheBloke

May 13, 2016 at 1:51 AM

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]

NUCLEAR RABBIT

May 16, 2016 at 9:55 PM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.