Recently I have become overly enthused about algorithm developed and design which has led me to initiate a ten day segment on sorting algorithms. Over the next few weeks the I will share pseudo code, explanations and also C++ source code for ten different sorting algorithms. Each sorting algorithm has advantages and disadvantages over others which will also explained and asset your knowledge when deciding which sort to use. Sorting algorithms that will be covered during this segment will include: Bubble Sort, Quick Sort, Bogo Sort, Cocktail Sort, Pigeonhole Sort, Heap Sort, Insertion Sort, Merge Sort, Order Sort and the Selection Sort. So to kick off day one of this segment – I will start with the most commonly and easiest sorting algorithm to learn – the Bubble Sort.

Bubble Sort

The Bubble sort is a simple comparison sort algorithm. The Bubble sort is commonly taught to high school students within a computer science class in languages such as Java, Visual Basic and Turing. The algorithm works by repeatedly stepping through the list to be sorted, comparing each adjacent items and swapping them for the appropriate order. The Bubble sort continuously iterates over the list swapping items when needed until there are no swaps required.

At the start, you should assume that this algorithm works exactly how it is named; the smaller elements bubble to the top of the list and the larger items sink to the bottom.

procedure BubbleSort( A )
    for pass ? 1 to length( A ) - 1 do
        for i ? 1 to length( A ) - 1 do
            if A[i] < A[i - 1]
                then swap A[i] ? A[i - 1]

Alright. We now know what the basic Bubble Sort algorithm looks like in pseudo code which is provided above. Now for an actual implementation. Below is an implementation of the Bubble Sort used for sorting a standard template library container named a Vector.

template<typename T>
void BubbleSort(std::vector<T> *A)
{
	for( std::vector<T>::size_type i = 0; i < A->size() - 1; ++i )
	{
		for( std::vector<T>::size_type j = 0; j < A->size() - 1; ++j )
		{
			if( A->at(j) > A->at(j + 1) )
			{
				std::swap(A->at(j), A->at(j + 1));
			}
		}
	}
}

Remember, the Bubble Sort is one of the worst sorting algorithm that is commonly used. This is due to the repeated iterations and comparisons done by the algorithm until no swaps are required. However, that being said the Bubble sort has one significant advantage over other implements (even the QuickSort) is that the ability to detect that the list is sorted is efficiently built into the algorithm.

As this is the first sorting algorithm out of many to come, I have not went into a great detail as most already know this one (even Barack Obama). Within the other posts soon to come, I will be sure to include more then one implementation and also discuss the Big O notation about each.