What is bubble sort in Python?

Overview

As programmers, we’re likely to come up against data structure and algorithm questions when going for job interviews. This helps companies make sure they hire a systematic problem-solver developer.

In this shot, we’ll learn about one of the simplest sorting algorithms, bubble sort. We’ll learn how it works, and how we can implement it in Python.

The bubble sort in a nutshell

Bubble sort is used to repeatedly compare adjacent items in a list and exchange them if they are in the wrong order.

Let’s consider a list that needs to be sorted in ascending order. To do this with bubble sort, we’ll start by comparing the first list item with the second. If the first item is greater than the second, we swap both items and compare the second and the third, and so on. So, for a list of size n, we need to repeat this process n - 1 times.

Note:

• Bubble sort is also called comparison algorithm.
• In real life, we can observe bubble sort when people in a queue swap their positions among themselves until everyone is standing based on increasing order of heights.

Let’s visualize an example of bubble sort for a better understanding of bubble sort.

Bubble sort in practice

Let’s consider this list of integer values: 19, 1, 9, 3, 10, 13. We want to sort it in ascending order.

First iteration

We start with the index 0 and 1: 19 > 1 is true. We swap both items.

Below is what the sorted list will look like:

Next, we compare the index 1 and 2: 19 > 9 is true. We’ll swap again.

Below is what the sorted list will look like:

We proceed with the index 2 and 3: 19 > 3 is true. Again, we swap these items.

Below is what the sorted list will look like:

Let’s continue the comparison with the index 3 and 4: 19 > 10 is true. We swap these items.

Below is what the sorted list will look like:

We proceed with the index 4 and 5: 9 > 13 is true. We’ll swap.

Below is what the sorted list will look like:

This is the end of the first iteration. We can notice how the newly formed, sorted list is in ascending order. 1, 9, 0, 13, 19.

Second iteration

In the second iteration, we do the same thing as we did in the first iteration.

We start with the index 0 and 1: 1 > 9 is false. We don’t need to swap.

Next, we proceed with the index 1 and 2: 9 > 3 is true. We swap.

Below is what the list will look like after swapping:

Finally, every item is in its right position. This marks the end of the process.

Note: If the list does not sort as expected, we continue with the sorting processes until we get a fully sorted list.

Bubble sort: Pseudocode

It’s always a good practice to use pseudocode before actual implementation. Below is the pseudocode for bubble sort.

function bubbleSort(array)
Set isSwapped to true
WHILE isSwapped = true
    Reset isSwapped to false
    FOR each item in the array
        IF current-item > next-item
            swap items
            Reset isSwapped to true
        ENDIF
    ENDFOR
ENDWHILE
RETURN array

Bubble sort: Python implementation

Now, we’ll implement the bubble sort algorithm in Python.

Our method of implementation is not that complicated. We’ll go through a list of integers by comparing adjacent items to see if they need to be swapped. If so, we swap them.

Let’s get started.

We create a boolean variable, isSwapped, and initialized it to true. By doing so, it allows us to use it in a while loop. Inside the while loop, we first assume that we need swapping, so we set isSwapped to false. If we swap, we reset it back to true.

Congratulations! Our implementation of the bubble sort algorithm in Python is successful.

Note: If you want to change the sorting order from ascending to descending, all you have to do is change the > operator at line 8 with the < operator; the rest of the code will remain the same.

Complexity analysis

On a final note, let’s look at one last anecdote on the performance of this algorithm.

Bubble sort is a straightforward sorting algorithm and a prolonged one. Due to that, we’ll rarely find or use it in the real world. It is used primarily for educational purposes.

• Worst CaseIf the array is not sorted. Time Complexity: $O(n^2)$
• Best CaseIf the array is sorted. Time Complexity: $O(n)$
• Average CaseIf the array is partially sorted. Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

Happy coding!