What are the disadvantages of bubble sort?

Answer 1

The advantage of sorting is that it is quicker and easier to find things when those things are organised in some way. The disadvantage is that it takes time to sort those things. In computing terms, the cost of searching a few unsorted items is minimal, but when searching a large number of items (millions or perhaps billions of items), every search will have an unacceptable cost which can only be minimised by initially sorting those items. The cost of that sorting process is far outweighed by the speed with which we can subsequently locate items. Inserting new elements into a sorted set also incurs a cost, but no more than the cost of searching for an element, the only difference is we search for the insertion point rather than a specific element.

Answer 2

Bubble sort is fine when dealing with small lists, with fewer than around 20 items. Time complexity is O(n^2) but this can be reduced to O(n!) by ignoring the last item from each previous pass (since it is guaranteed to be sorted). And by keeping track of the last swap in the previous pass, the big O can be reduced even further, averaging O(n!/2). A fully-optimised bubble sort would then take linear time O(n) to process an already sorted list. Other advantages include tiny code size, stability (equal items maintain their sequence) and minimal auxiliary memory.

For more than 20 items, other methods such as quick-sort prove to be faster on average O(n log n) for anything other than an already sorted list O(n^2). For relatively small lists, the difference is insignificant, but for larger data sets, the difference soon becomes visibly evident.

Unless your list has some way to determine if the list is already-sorted in constant time (maintaining a flag every time unsorted items are inserted, for instance), a hybrid sort is worth consideration. A hybrid sort makes an initial pass using bubble-sort. If no changes are detected, then the list is already sorted, otherwise a more efficient algorithm completes the sorting process.

See related links below for a comparison of sorting algorithms.

Answer 3

Advantage, easy to code.

Disadvantage, it runs in Big-Theta(n2) time.