Asked in C ProgrammingComputer ScienceC++ Programming
What is bubble sort?
May 12, 2012 12:42PM
Bubble sort is a sorting algorithm that compares 2 adjacent items at a time, starting from the beginning of a list, and swapping them if they are out of sequence. Each comparison gradually moves the largest item to the end of the list (likened to a bubble making its way to the surface of water). After n*n passes, all the items will be sorted. The big O for a standard bubble sort is therefore O(n*n).
The algorithm can be improved somewhat. Since it is clear that the last item is sorted on each pass, the unsorted set can be reduced by 1 element on each pass. Moreover, since the final swap on each pass indicates that everything from that point on is already sorted, the unsorted set can often be reduced by more than 1 element on each pass. For an already sorted list, the worst case is reduced to O(n), constant time.
For small sets of data, perhaps 10 to 20 items, the bubble sort is reasonably efficient, especially on partially sorted lists. However the insert sort algorithm offers similar or better performance on average. With larger sets, the quick sort algorithm is hard to beat, but is let down by inefficiencies when dealing with partially sorted lists. Hybrid sorts can improve things a little, however, there is no efficient way to check the state of a list to determine the most efficient algorithm to use at any given point.