Skip to content

Bubble Sort: A Simple and Efficient Sorting Algorithm for Python

Updated: at 05:24 AM

Bubble Sort is one of the simplest and most intuitive sorting algorithms in computer science. This beginner-friendly 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)

     swapped = false
     for i = 1 to indexOfLastUnsortedElement-1
       if list[i] > list[i+1]
         swap(list[i], list[i+1])
         swapped = true
   until not swapped
end procedure

Let’s break this down step-by-step:

  1. Start looping from the beginning of the list to be sorted.
  2. Compare the current element (list[i]) with the next element (list[i+1]).
  3. If list[i] > list[i+1], the elements are not in the intended order. Swap them.
  4. Set swapped = true to indicate that a swap occurred.
  5. Move to the next pair of elements and repeat steps 2-4 until reached the end of list.
  6. If no swaps occurred during the last pass, the list is now sorted. Otherwise, repeat steps 1-5.

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

Bubble sort has a quadratic time complexity in the average and worst cases.

Space Complexity


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]

# 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:

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 real-world applications due to its slow O(n^2) time complexity on average.

Bubble sort is most appropriate when:

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:



While bubble sort is versatile, its O(n^2) time complexity limits its usefulness for many real-world 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:

Bubble Sort Applications

Here are some examples of when bubble sort could be applied:

Alternatives to Bubble Sort

For most real-world use cases where efficiency is important, bubble sort is not ideal due to its slow run time. Some common alternatives are:

Choosing an appropriate high-performance sorting algorithm like merge sort, quicksort, or timsort is recommended for most production use cases.


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.