Lets Blow Bubbles in C++, the Bubble Sorting way!

Now dip the wand into the soap and take it back out, blow gently and voila! Your integer array is sorted! Wow, only if it was that easy huh? Well it can be with a simple straight forward demonstration of bubblesorting. In this entry I will attempt to quickly show you a simple bubblesort you can do at home and in your own projects. It may even help you pass your first assignment in your computer science program. It isn’t hard…. I show you how in this entry of the Programming Underground!

Weeeeee! Look at all the bubblesorting going on in the world! I have been cruising the Dream.In.Code forums and I have noticed A LOT of people asking about their sorting and why it isn’t working. When I check it out, they are simply trying for a bubblesort and having problems either with the loops or with the actual idea of swapping compared values. So I thought to myself “Why not show a brief example of how it works and provide everyone with a copy to use for themselves?” Sometimes I believe the best way to learn is to see some examples in action!

Now keep in mind that while most examples do show you an integer array, you could very easily use any kind of array as long as you know how to adequately compare them to tell which one is greater and needs to be moved as they are sorted.

This BubbleSort function can also be easily adapted over to Java and C# with very little changes. So if you specialize in those languages you should find this useful as well. I would have included it in my definitive series, but I don’t exactly have a whole lot of time right now. I may still do it in the future though as time permits.

In the example below I have created a nice simple 10 digit integer array and initialized it with some numbers in random order. I print them out to first show that they are all jumbled. I then call our BubbleSort function and print the array again to show you they are sorted. Keep in mind that in C++ arrays are automatically passed by reference so this example doesn’t need anything tricky like needing pointers and such. It works just fine as it is.

#include <iostream>	
using namespace std;

// Define our bubblesort to take an integer array and its size.
void BubbleSort(int [], int);

int main()
{
	// Load array and print it to screen.
	int test[10] = {8,4,5,6,2,1,9,0,7,3};
	for (int i = 0; i < 10; i++) {
		cout << i << ". " << test[i] << endl;
	}

	cout << "\nSorting our numbers...\n" << endl;

	// Call the sort
	BubbleSort(test,10);

	// Print the array again.
	for (int i = 0; i < 10; i++) {
		cout << i << ". " << test[i] << endl;
	}

	return 0;
}

// Classic BubbleSort using while loop. 
void BubbleSort(int arSort[], int size) {
	bool swap = true;

	// Keep going as long as a swap has occurred.
	while (swap) {

		// Start with false once inside the loop
		// We will set it true upon detection of swap
		// It will tell the loop to make another pass.

		swap = false;

		// Notice we subtract one from the size because of the subscripts.
		// If the size is 10, we need to make it go through 0 - 8 subscripts
		// Why? Because we have the test i + 1, which means when it is 8
		// it will be 8 + 1 or 9, our highest subscript for 10 elements.

		for (int i = 0; i < size - 1; i++) {
			if (arSort[i] > arSort[i + 1]) {
				int temp = arSort[i];
				arSort[i] = arSort[i + 1];
				arSort[i + 1] = temp;
				swap = true;
			}
		}
	}
}

I have severely commented this program just to give you an idea of what I am doing and why. Some of the points to note are the use of two loops, one to detect if another pass through the entire array is needed and an inner one to actually loop through comparing each value against the one next to it. Another thing to note is the subtraction of 1 from the size variable. This is done because during our comparisons we add one to the counter. If we had left this alone as just “size” we would eventually get to the end of the array (where the subscript is 9, remember 10 elements are subscripts 0 – 9) and it would have gone 9 + 1 = 10 and attempted to use subscript 10, which is not available.

This off by one error is what usually gets a lot of people first starting out in programming so keep it in mind when you need to loop. Since a swap is made, we set our boolean “swap” to true to tell the outer loop that a switch was made and to go through the array again. The sort is finished when the inner loop moves through the entire array and no swaps have been made. It then terminates and the array is sorted.

That is all there is to it! Try the example out for yourself and if you can, step through it line by line. Reading each line should make logical sense and keep this in the back of your mind so that whenever you need a quick sort algorithm, you can pull this out without even needing to look it up!

I hope you find this code useful and feel free to use it in your projects whenever you want. I throw it out to the world and our DIC members. Enjoy and hope you had fun reading this blog entry. Oh and remember, don’t drink the bubble soap or you will be spitting bubbles for a long time. It might sound cool, but take it from me, when you need to curse someone out on the street, it doesn’t help your cause when bubbles keep coming out of your mouth. Makes you look like a panzy.

🙂