Bubble Sort is one of the simplest and most intuitive sorting algorithms in computer science. This beginnerfriendly algorithm works by repeatedly comparing adjacent elements in a list and swapping them if they are out of order. The process is repeated until the list is completely sorted.
Table of Contents
Open Table of Contents
Understanding Bubble Sort
Before we dive into the Python implementation, let’s first build an understanding of how the Bubble Sort algorithm works and analyze its time and space complexities.
How Bubble Sort Works
Bubble Sort iterates through a list, compares adjacent elements, and swaps them if they are not in the intended order.
The pseudocode for Bubble Sort is:
procedure bubbleSort(list)
repeat
swapped = false
for i = 1 to indexOfLastUnsortedElement1
if list[i] > list[i+1]
swap(list[i], list[i+1])
swapped = true
until not swapped
end procedure
Let’s break this down stepbystep:
 Start looping from the beginning of the list to be sorted.
 Compare the current element (list[i]) with the next element (list[i+1]).
 If list[i] > list[i+1], the elements are not in the intended order. Swap them.
 Set swapped = true to indicate that a swap occurred.
 Move to the next pair of elements and repeat steps 24 until reached the end of list.
 If no swaps occurred during the last pass, the list is now sorted. Otherwise, repeat steps 15.
Bubble sort gets its name because smaller elements slowly “bubble” their way up to the beginning of the list, just like bubbles in a glass of water rise to the top.
Analysis of Bubble Sort
Let’s analyze the time and space complexity of Bubble Sort to understand its performance.
Time Complexity

Best Case: O(n) when the list is already sorted. Only one pass through the list is needed.

Average Case: O(n^2) as the simple Bubble Sort implementation makes multiple passes through the entire list.

Worst Case: O(n^2) when the list needs to be fully sorted by making multiple passes.
Bubble sort has a quadratic time complexity in the average and worst cases.
Space Complexity
 Space: O(1) constant space. Only a single additional memory space is needed for the temp variable used for swapping.
Stability
 Bubble sort is a stable sorting algorithm since it does not change the relative order of elements with equal values when sorting.
Implementing Bubble Sort in Python
Let’s look at how to implement bubble sort in Python, starting with a simple implementation and then optimizing it.
Simple Implementation
Here is a simple implementation of the bubble sort algorithm in Python:
def bubble_sort(nums):
# We set swapped to True so the loop looks runs at least once
swapped = True
while swapped:
swapped = False
for i in range(len(nums)  1):
if nums[i] > nums[i + 1]:
# Swap the elements
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# Set the flag to True so we'll loop again
swapped = True
random_list_of_nums = [5, 2, 1, 8, 4]
bubble_sort(random_list_of_nums)
print(random_list_of_nums)
# Printed: [1, 2, 4, 5, 8]
This follows the bubble sort pseudocode directly. We iterate through the list while swapping any adjacent elements that are out of order, repeating this process until the list is fully sorted.
Optimized Implementation
We can optimize the above simple implementation by stopping the algorithm early if there were no swaps done in the last pass. This means the list is already fully sorted and no further processing is required.
def bubble_sort(nums):
swapped = True
# Keep running the steps while swapped
while swapped:
swapped = False
for i in range(len(nums)1):
if nums[i] > nums[i+1]:
# Swap
nums[i], nums[i+1] = nums[i+1], nums[i]
swapped = True
# If nothing was swapped last pass
# array is sorted  break early
if not swapped:
break
This optimized bubble sort reduces the average time complexity to O(n) from O(n^2).
When to Use Bubble Sort
Due to its simplicity, bubble sort is often one of the first algorithms taught in introductory computer science courses. However, it is rarely used in realworld applications due to its slow O(n^2) time complexity on average.
Bubble sort is most appropriate when:
 Simplicity and ease of implementation is preferred over efficiency.
 The input list is already nearly sorted. Bubble sort will run fastest in this case.
 Only a few elements need to be sorted. The algorithm will not take long on a small list.
It is generally not recommended to use bubble sort for sorting large data sets due to performance concerns. The optimized bubble sort discussed above improves efficiency for nearly sorted lists.
Benefits and Drawbacks of Bubble Sort
Bubble sort has some advantages that make it suitable for certain use cases:
Benefits:
 Simple to understand and implement
 Stable sorting algorithm
 Low memory overhead
Drawbacks:
 Very slow for large datasets
 Not efficient for sorting nearly sorted data
 Poor performance on average case
While bubble sort is versatile, its O(n^2) time complexity limits its usefulness for many realworld sorting tasks with large data. The slow speed makes it unsuitable for production use cases where performance is critical.
Optimizing Bubble Sort
There are a few ways we can optimize the bubble sort algorithm:
Stop early if no swaps:
Check if any swap occurred in the last pass. If not, the list must already be fully sorted and we can stop the algorithm early. This optimization improves the best case to O(n).
Use a sentinel node:
Adding a dummy sentinel element at the end removes the need to check for end of list. This avoids index out of bound errors.
Bidirectional bubble sort:
The list is sorted in both directions for faster sorting. Starts from left to right and then right to left.
Cocktail shaker sort:
A bidirectional variant that also utilizes idea of selection sort by finding both minimum and maximum simultaneously. This further improves optimization.
Bubble Sort Variations
There are several modified versions of bubble sort that improve performance:

Comb sort  Compares elements separated by a gap of size more than 1. This gap is gradually decreased based on a shrink factor.

Oddeven sort  Performs parallel bubble sort on odd and even indexed elements. Achieves stable sort.

Gnome sort  Similar to bubble sort but makes the first gap very large so that initially it behaves like an insertion sort.

Cocktail shaker sort  Bidirectional variant of bubble sort that sorts in both directions on each pass.
Bubble Sort Applications
Here are some examples of when bubble sort could be applied:

Educational Purposes: Demonstrate the basic idea behind comparison sorting algorithms.

Sorting Small Arrays: For lists with just a few elements, the overhead of O(n^2) may not be significant.

Nearly Sorted Data: An optimized bubble sort can improve speed when the input data is already close to being fully sorted.

Embedded Systems: Spaceconstrained environments may use bubble sort due to its low memory requirements. Slower processing is a tradeoff.
Alternatives to Bubble Sort
For most realworld use cases where efficiency is important, bubble sort is not ideal due to its slow run time. Some common alternatives are:

Insertion Sort: More efficient most of the time at O(n) on nearly sorted data but still O(n^2) worst case.

Selection Sort: O(n^2) time complexity but lower overhead than bubble sort. Useful for small lists.

Merge Sort: A divideandconquer algorithm with O(n log n) time complexity. Much faster than bubble sort.

Quicksort: A popular inplace divideandconquer sort with O(n log n) average time. Has O(n^2) worst case.

Timsort: A hybrid stable sort used in Python and Java. It performs admirably on realworld data by combining merge sort and insertion sort.

Heapsort: An inplace O(n log n) algorithm that sorts by building a heap data structure. Speed optimizations possible.
Choosing an appropriate highperformance sorting algorithm like merge sort, quicksort, or timsort is recommended for most production use cases.
Conclusion
Bubble sort is an elementary sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are out of order.
While easy to understand and implement in languages like Python, its O(n^2) time complexity makes it unsuitable for large datasets. The simplicity of bubble sort still makes it a worthwhile educational tool.
With some optimizations, bubble sort can provide faster sorting of small arrays or nearly sorted lists where absolute efficiency is not required. However, for most use cases, more advanced algorithms like quicksort are preferred.
I hope this guide gave you a comprehensive introduction to implementing bubble sort in Python! Let me know if you have any other questions.