Programmers who switch from PC and web development into coding for mobile devices or embedded systems find that more time is spent selecting and coding their own data structures and algorithms. With less memory and limited data storage, there is no room for pre-built libraries or frameworks. So for those who need to write their own sorting routines, here are some considerations on choosing the lowly bubble sort.
Background
Video of the Day
The bubble sort is a simple algorithm that sorts a list of items in memory. Given an array, the code repeatedly compares each pair of adjacent items and swaps them if they are not in order. The process repeats until no more swaps occur. If it were possible to view the array while the sort is in progress, the low values would "bubble" to the top while the large values would sink to the bottom. Here is the relevant code in Visual Basic 2010:
Video of the Day
While swap = True swap = False For i = 0 To tbl.length - 2 If tbl(i) > tbl(i + 1) Then tmp = tbl(i) tbl(i) = tbl(i + 1) tbl(i + 1) = tmp swap = True End If Next End While
When to Choose the Bubble Sort
This algorithm has several advantages. It is simple to write, easy to understand and it only takes a few lines of code. The data is sorted in place so there is little memory overhead and, once sorted, the data is in memory, ready for processing. The major disadvantage is the amount of time it takes to sort. The average time increases almost exponentially as the number of table elements increase. Ten times the number of items takes almost one hundred times as long to sort.
Other Array Sorts
Sorting algorithms vary in complexity, speed and overhead. The bubble sort is the least complex but also one of the slowest. Other array-based sorts like the insertion sort and exchange sort are a little faster but take more code (see the references below). The main advantage of array-based sorts are that they use the least code and take the least amount of working memory. Consider these sorts for simple arrays with less than a few hundred items.
Complex Sort Algorithms
Larger data sets require more complex code and more memory. The quick sort and heap sort both split and copy the data sets to optimize the number of comparisons. The quick sort continually divides the list then reassembles it in sorted order. The heap sort copies the data into a tree structure then traverses the tree to copy the data back into order. Both are fast and efficient but take more code and much more working storage. Choose these algorithms for large data sets.