In this algorithm video tutorial, we covered the bubblesort algorithm. Bubblesort is the simplest sorting algorithm and is useful for illustrating algorithmic concepts. As a sorting routine, the bubblesort is slower than most other sorting routines.

Sorting is one of the most common operations in programming; it is used everywhere from email programs to databases, wherever there is a list of data. For example, if we own a business, we will want to be able to find customers or determine which products are selling well. To do this efficiently requires sorting. Below, we have a list of four company names which we sort alphabetically with a bubblesort. Only the sequence of actual swaps is shown:

The bubblesort algorithm applied to this list of four names can be illustrated graphically in a sequence like this:

The dark gray represents a comparison and the white represents a swap. We mentioned in the video that the bubblesort has n-squared time complexity and we only talked about the number of comparisons, not swaps. When analyzing algorithms, we always calculate the complexity from the most numerous steps. In the image above, we can see that every swap has a comparison prior to it, but not every comparison is followed by a swap. In the bubblesort, there are always at least as many comparisons as swaps.

Complexity is used to measure the efficiency of an algorithm. The notion and terminology associated with algorithmic complexity comes from mathematical analysis. Once we have a few more algorithms under our belt and the intuitive notion of complexity is established, we will formalize the idea and make it more rigorous.

#include <iostream>

void main() {
	using namespace std;

	double daArray[] = {2.5, .7, 9.7, 6.5, 3.4, 1.8};
	int iLength = 6;

	// Output the unsorted array
	cout << "Initial Array: ";
	for (int iIndex = 0; iIndex < iLength; ++iIndex) {
		cout << daArray[iIndex] << "  ";
	}
	cout << endl;

	// The Bubblesort
	for (int iEnd = iLength - 1; iEnd > 0; --iEnd) {
		for (int iIndex = 0; iIndex < iEnd; ++iIndex) {
			// Check if the elements are out of order and swap them, in needed.
			if (daArray[iIndex] > daArray[iIndex + 1]) {
				double dTemp		= daArray[iIndex];
				daArray[iIndex]		= daArray[iIndex + 1];
				daArray[iIndex + 1]	= dTemp;
			}
		}
	}

	// Output the sorted array
	cout << "Sorted Array: ";
	for (int iIndex = 0; iIndex < iLength; ++iIndex) {
		cout << daArray[iIndex] << "  ";
	}
	cout << endl;
}

The C++ code for the bubblesort, using an array of six doubles, is given above. If we compile and execute this, we see the output below.