A Python bubble sort goes through a list and compares elements next to each other. If an element on the right is greater than one on the left, the elements are swapped. This happens until the list is sorted.
Do you need to sort a list? The bubble sort has got your back. The bubble sort is a type of standard algorithm that sorts 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.
Python Bubble Sorts
A bubble sort compares pairs of adjacent elements and swaps those elements if they are not in order. It is commonly implemented in Python to sort lists of unsorted numbers. Bubble sorts are a standard computer science algorithm.
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 is checked. Then, a bubble sort will loop through the list again. This occurs until no more swaps need to be performed.
When Should You Use a Bubble Sort in Python?
Bubble sorts are a good sorting method to use when you’re just starting to learn about sorting algorithms. 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 Algorithm Python: Walkthrough
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 we swap these two elements.
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 we swap the two numbers:
Reaching the End of a List
Our list is already starting to look sorted. But we’ve reached the end of our list and it is not 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 the list is sorted. We call each time the list starts sorting values from the beginning a pass. In this example, our bubble sort will compare 7 and 4. 7 is greater than 4, so we swap the elements:
Our algorithm compares 7 and 12. No swap is necessary, so we’ll move on. We compare 12 and 19. 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 every swap has taken place.
Bubble Sort Python Program
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.
Let’s begin by writing a Python 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 a Python “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 Python array 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 Python “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]
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 Python 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
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.
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.
To learn more about algorithm complexity, check out our Career Karma Big O Notation guide.
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. Bubble sorts are a good introduction to sorting algorithms. You can use them to help familiarize yourself with algorithms before you learn about more advanced methods of sorting, such as an insertion sort.
For expert guidance on Python resources and courses, check out our How to Learn Python guide.
About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Read more