Bubble Sort Algorithm in Python: Code, Example & Complexity
This Snippet is coded by a user inOnline python Compiler. You can see and run this code too.
زبان: python
How Bubble Sort Works
Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through a list, compares adjacent items, and swaps them when they are in the wrong order. During each pass, compare adjacent elements and swap if the left value is greater than the right value. Repeat until no swaps occur or the unsorted section has one element left. After each pass, the largest remaining value “bubbles” to the end of the unsorted section. The Python implementation below sorts a list in place and returns it. Pass a list of comparable values, such as integers or strings; the output is the same list arranged in ascending order. An early-exit flag stops the algorithm when a pass makes no swaps, which improves best-case performance.
Example
Input: [64, 34, 25, 12, 22, 11, 90]
Output: [11, 12, 22, 25, 34, 64, 90]
Time and Space Complexity
- Best case: O(n) when the list is already sorted and the early-exit optimization is used.
- Average case: O(n²) due to nested comparisons.
- Worst case: O(n²) when the list is reverse sorted.
- Space complexity: O(1) auxiliary space because sorting happens in place.
Bubble Sort is easy to understand and useful for teaching, but it is inefficient for large datasets. For production code, prefer Python’s built-in sorted() or list.sort(), which use efficient algorithms.