As you were writing Bubble Sort, you may have realized that we were doing some unnecessary iterations.
Consider the first pass through the outer loop. We’re making
nums = [5, 4, 3, 2, 1] # 5 element list: N is 5 bubble_sort(nums) # 5 > 4 # [4, 5, 3, 2, 1] # 5 > 3 # [4, 3, 5, 2, 1] # 5 > 2 # [4, 3, 2, 5, 1] # 5 > 1 # [4, 3, 2, 1, 5] # four comparisons total
We know the last value in the list is in its correct position, so we never need to consider it again. The second time through the loop, we only need
As we correctly place more values, fewer elements need to be compared. An optimized version doesn’t make
n^2-n comparisons, it does
(n-1) + (n-2) + ... + 2 + 1 comparisons, which can be simplified to
(n^2-n) / 2 comparisons.
This is fewer than
n^2-n comparisons but the algorithm still has a big O runtime of
As the input,
N, grows larger, the division by two has less significance. Big O considers inputs as they reach infinity so the higher order term
N^2 completely dominates.
We can’t make Bubble Sort better than
O(N^2), but let’s take a look at the optimized code and compare iterations between implementations!
We’re also taking advantage of parallel assignment in Python and abstracting away the
Run the code and marvel at the increased efficiency!