Do you need to sort a list? The bubble sort has got your back. The bubble sort is a type of standard algorithm that is used to sort lists. It is perhaps the simplest sort out there, so it’s perfect for beginners who are new to sorting algorithms!
In this guide, we’re going to discuss how bubble sorts work and how you can implement a Python bubble sort algorithm. We’ll go through an example so that you understand how each part of a bubble sort works. Let’s begin!
How Do Bubble Sorts Work?
A bubble sort compares pairs of adjacent elements and swaps those elements if they are not in order.
By using a bubble sort, you can sort data in either ascending or descending order. Starting from the first element in a list, a bubble sort will compare the first and second elements. If the first element is greater than the second, a swap occurs.
This process is repeated until every item in a list has been checked. Then, a bubble sort will loop through the list again, until no more swaps need to be performed.
When Should You Use a Bubble Sort?
Bubble sorts are a good sorting method to use when you’re just starting to learn about sorting algorithms. Whereas algorithms like selection sorts require more logic, a bubble sort is a simple way to sort a list of items that do not appear in order.
Bubble sorts work best when you have a list with only a few objects. This is because when a bubble sort only has to make a few comparisons, it is very quick. When you need to sort a larger list, there are more efficient algorithms that you can use. Most developers would opt to use a method like an insertion sort to sort a longer list of items.
Bubble Sort Guide
Let’s get into the weeds and start to walk through how a bubble sort works. We’ll start with the following list, whose elements appear in the wrong order:
Our bubble sort starts by comparing the first and second elements in our list. If the first element is greater than the second, then these two elements are swapped.
In this example, we are going to compare 7 and 19. 7 is not greater than 19, so it stays in the same place. Our list now looks the same as it did before:
We’ll now go on to compare the second and third elements in our list. 19 is greater than 4, which means that we need to swap them. Our list now looks like this:
We can now compare the third and fourth items in our list. 19 is greater than 12, so the two numbers are swapped:
Our list is already starting to look sorted. But we’ve reached the end of our list and it hasn’t been fully sorted. What’s going on? Bubble sorts make multiple passes through a list, which means that they keep running until every item in a list is sorted.
Our bubble sort will start from the beginning again until all the elements are sorted. We call each time the list starts sorting values from the beginning a pass. In this example, our bubble sort wil compare 7 and 4. 7 is greater than 4, so it is moved:
Our algorithm will compare 7 and 12. No swap is necessary, so we’ll move on. 12 and 19 are compared, and again no swap is necessary. Now that we’ve reached the end of our list, it’s clear that no more swaps need to be made.
Did you notice that our algorithm kept going even after our list sorted? That’s because a bubble sort will continue to swap elements until it compares every item in a list for each item in the list. Our algorithm will not stop until all of these swaps have been performed.
How to Write a Python Bubble Sort
Up until now we’ve been swapping numbers in a table. It’s true that we managed to sort our list, but we don’t have to do this manually. Bubble sorts are a computing algorithm after all; let’s get a computer to run the algorithm for us.
A bubble sort can be written in vanilla Python, which means that you don’t need to depend on any external libraries to write a bubble sort.
FREE Python Fundamentals Workshop
Use the calendar below to reserve your seat.
Demand for people who know Python is soaring! In this free online workshop, learn the fundamentals of Python and meet other Career Karma members who are building with Python.
Let’s begin by writing a function that sorts a list of numbers in ascending order:
def sortList(array): for item in range(len(array)): for j in range(0, (len(array) - item - 1)): if array[j] > array[j + 1]: (array[j], array[j + 1]) = (array[j + 1], array[j])
Our algorithm starts with a for loop. This loop iterates through every item in our array. Then, we use another for loop to compare all the items in our array with each other.
In our code, we’ve defined an “if” statement which checks whether a given item is larger than the next item in the list. This “if” statement will perform comparisons such as:
- Is the first item in the list greater than the second?
- Is the second item in the list greater than the third?
Our code isn’t finished yet. If you try to run the above Python program, nothing will happen. We’ve got to call our function and give it some data:
numbers = [7, 19, 4, 12] sortList(numbers) print("List in order:", numbers)
Our code returns:
List in order: [4, 7, 12, 19]
We did it! Our list is sorted in ascending order! You can use a bubble sort to sort a list in descending order. To do so, swap the greater than sign with a lesser than sign in the “if” statement:
if array[j] < array[j + 1]:
When we run our program with this revised line of code, the following is returned:
List in order: [19, 12, 7, 4]
The average time complexity of the bubble sort is O(n^2). This happens when the elements in an array are unsorted.
In the worst case, a bubble sort performs at O(n^2). This happens when an array is already in ascending or descending order and needs to be sorted the opposite way. In the best case, this algorithm will perform at O(n). This happens if an array is already sorted.
Optimizing the Bubble Sort
Earlier on we talked about how every possible comparison is made even if our list is sorted. This makes our bubble sort quite inefficient: it keeps going even after the list is sorted.
While it doesn’t make a big difference in this example, at scale this could impact the execution time of a program. That’s where the optimized bubble sort comes in.
We can optimize our bubble sort by writing a new variable. Let’s call it
swap. This variable will track whether any swaps have taken place in a
for loop. If this variable is set to false, then it means that our list is sorted; no more iterations need to happen.
Let’s revise our sortList function from earlier:
def sortList(array): for item in range(len(array)): swap = True for j in range(0, (len(array) - item - 1)): if array[j] > array[j + 1]: (array[j], array[j + 1]) = (array[j + 1], array[j]) swap = False if swap == True: break
In this code, we’ve defined a variable called
swap which has the default value: True. This is contained within our first
for loop because it keeps track of whether a swap has occurred on each pass through the list. If our array makes a comparison, the value of
swap is set to False.
If there is no swap made in the last swap, then the array is already sorted. Our list will then check whether
swap is equal to True. If it is, our program will stop executing.
Let’s run our code again:
List in order: [4, 7, 12, 19]
Our data has been sorted the same way but our algorithm is now faster and more efficient. Our algorithm now stops as soon as all the items in the list have been sorted.
Bubble sorts provide a simple way in which you can sort a list of data. They can be used to sort data in either ascending or descending order.
This algorithm is most commonly used when you need to sort a small list. It’s also a good introduction to sorting algorithms that you can use before you learn about more advanced methods of sorting, such as an insertion sort.
Now you’re ready to write your own bubble sort algorithm in Python like an expert!