Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bubble
algorithm
python
sort
communitycreator

What is bubble sort in Python?

Abel Lifaefi Mbula

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.

List of indexes

First iteration

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

Swapping item 1 and 2

Below is what the sorted list will look like:

The new list after swapping item 1 and 2

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

Swapping item 2 and 3

Below is what the sorted list will look like:

New list after swapping item 3 and 4

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

Swapping item 3 and 4

Below is what the sorted list will look like:

New list after swapping item 3 and item 4

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

Swapping item 4 and 5

Below is what the sorted list will look like:

New list after swapping item 4 and 5

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

Swapping item 5 and 6

Below is what the sorted list will look like:

New list after swapping item 5 and 6

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.

1 is less than 9, we don't swap

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

Swapping item 2 and 3

Below is what the list will look like after swapping:

New list after swapping item 2 and 3

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 a 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. Let’s get started.

def bubbleSort(list):
  for i in range(len(list) - 1):
    if(list[i] > list[i + 1]):
      temp = list[curr_index]
      list[curr_index] = list[curr_index + 1]
      list[curr_index + 1] = temp
Initial bubbleSort()

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.

  • First, we keep the left item in a temporary variable, temp.
  • Next, we assign the value of the right item to the left one.
  • Lastly, we assign the right item, temp.

To make our code clearer and more readable, let’s use the swap() method.

def swap(list, curr_index):
   temp = list[curr_index];
   list[curr_index] = list[curr_index + 1]
   list[curr_index + 1] = temp

Our code works fine, but only for one iteration, which is not enough to sort the list as expected.

Let’s modify the code so that it can loop over and over until we get a fully sorted list.

# Bubble sort: Python implementation by Abel

def bubbleSort(list):
  isSwapped = True

  while(isSwapped):
    isSwapped = False
    for i in range(len(list) - 1):
      if(list[i] > list[i + 1]):
        isSwapped = True
        swap(list, i)
Use while loop to go through the list over and over

We’ve create a boolean variable, isSwapped, and initialize 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.

Let’s put it all together and run our code.

# Bubble sort: Python implementation by Abel

def bubbleSort(list):
  isSwapped = True

  while(isSwapped):
    isSwapped = False
    for i in range(len(list) - 1):
      if(list[i] > list[i + 1]):
        isSwapped = True
        swap(list, i)

def swap(list, curr_index):
   temp = list[curr_index];
   list[curr_index] = list[curr_index + 1];
   list[curr_index + 1] = temp;

# Test bubble sort
list = [ 19, 1, 9, 3, 10, 13 ]

bubbleSort(list)
print('Sorted array in ascending order:')
print(list)
Test our implementation

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

If you want to change the sorting order from ascending to descending, all you have to do is change the > operator at line 9 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(n2)O(n^2)
  • Best CaseIf the array is sorted. Time Complexity: O(n)O(n)
  • Average CaseIf the array is partially sorted. Time Complexity: O(n2)O(n^2)
  • Space Complexity: O(1)O(1)

Happy coding!

RELATED TAGS

bubble
algorithm
python
sort
communitycreator
RELATED COURSES

View all Courses

Keep Exploring