What is the minimum number of comparisons in bubble sort?

Answer 1

A bubble sort may have a range from O(n-1) for a pre-sorted array, to O(n2-n) for a poorly implemented bubble sort algorithm.

Given 20 elements, a best case scenario is 19 comparisons, and the worst case is 380 comparisons.

Answer 2

For an array of length n, there are n*n comparisons (n squared) in a bubble sort; however, the algorithm can be optimized to reduce the number of comparisons by keeping track of where the last swap occurs on each iteration of the outer loop. Everything after that point is already sorted, thus the next iteration can stop comparing once that point is reached.

Answer 3

For a sequence of n elements, the minimum number of comparisons is n-1 (a single pass) in bubble sort. However, this can only happen when the sequence is already in sorted order! The worst case is (n-1)! (or factorial (n-1)) when the sequence is in reverse order.

Bubble sort is often cited as an example of how NOT to write an algorithm. Insertion sort is demonstrably more efficient on small sequences but is also used in hybrid sorts of larger sequences (where large sequences are broken down into short sequences that can be efficiently sorted using insertion sort).