Python Bubble Sort Algorithm: Explained with Examples, code and Video
This will be a comprehensive article covering a wide range of algorithms.
Starting from the basics and the areas of most interest covered at university and job interview favorites, to lesser known algorithms.
The simple sorting algorithms start with bubble sort, selection sort and insertion sort.
We will use this simple example of a python list of numbers to show examples of the sorting algorithms.
To loop (or iterate) through the numbers in the list in python we use the index that starts at 0. Therefore this python code has the following output:
nums = [7,1,8,4,3,2]
for i in range(len(nums)):
print("i=",i,"nums[i]=",nums[i])i= 0 nums[i]= 7
i= 1 nums[i]= 1
i= 2 nums[i]= 8
i= 3 nums[i]= 4
i= 4 nums[i]= 3
i= 5 nums[i]= 2
Guide to Python Insertion, Selection, and Bubble Sort Algorithms
The first sorting algorithms that are taught at university are not efficient but it is important to understand them.
The logic, programming and coding skills used to understand and write these algorithms are so important they are often tested in job interviews.
So lets get to first understand them, then learn how to code them, and then also learn how efficient they are and compare them.
Bubble Sort Algorithm in Python
The bubble sort algorithm is a simple sorting algorithm that works by repeatedly swapping two adjacent numbers when they are in the wrong order.
Checking each number pair from left to right, it will order the numbers in several rounds, one less round than the amount of numbers in the list.
Although the bubble sort algorithm is simple, just looking at the code will not help us to develop our skills.
Let’s see the code, then explain the bubble sort algorithm with an example, followed by understanding the code. This way you will truly learn the bubble sort in python.
for j in range(len(nums)-1):
for i in range(len(nums)-1-j):
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]Phone users can swipe the screen to move sideways to view the code
Python Bubble Sort Explained
The bubble sort algorithm takes an unordered list of numbers and uses a method of swapping two numbers to result in a final list of numbers in order.
In a python list of numbers it is very easy to swap two of them.
Image these is a python list called ‘nums’ and you wanted to swap the position of the first and second numbers.
The python code below shows how to move the numbers at the beginning of the list with the indexes of 0 and 1, to the positions with indexes of 1 and 0.
Remember a python list starts with an index 0.
#swap numbers
nums[0], nums[1] = nums[1], nums[0]The bubble sort goes left to right and swaps numbers when the lower number is after a higher number.
I goes though the list on several passes to achieve the final goal of a sorted list. The easiest way to understand this is to see an example.
Bubble Sort Example
Here is an example of a python list of unordered numbers.
We move from left to right and compare two adjacent numbers, if a number is followed by a lower number we swap them.
For example, the first two numbers are 7 and 1. As 1 is lower than 7 we swap them so the first two numbers are now 1 and 7.
The next comparison is between 7 and 8, which are in order so there is no need to swap them.
We continue to move left-to-right through the numbers as follows:
Whatever the list of numbers we will always have the highest number in the final position after this first round of moves.
So now we can complete a second pass but without comparing the highest number in the final position. Here are the moves in the second stage:
Round 3:
Round 4:
We may not need it in this case but we will always finish a list of 6 numbers in 5 rounds (the length of the list minus 1).
So what did we do and what python code represents these actions:
- loop through the loop (iterate) an amount of time one less than the list length
- Compare a number with the number in the next position
- Swap numbers if required
for i in range(len(nums)-1):
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]In the python code snippet above we use a for loop to iterate through the list, but one less than the list length, using range. The variable i will start at 0 and go 5 in this case. We use this variable i as an index to each item in the list.
The position i is used to look at a number and compare it to the number after it, so position i compared to position i+1.
Finally, if the lower number is after the number at position i, then the numbers are swapped. This completes one round of comparing numbers.
For each round there needs to be less comparisons as each round puts the highest number in the ‘next’ highest position. In our example you can see each round and the highest numbers in their correct position:
Video Tutorial
Bubble sort in python code
To summarize. We need a loop that iterates through each round which is one less than the list length. Lets use the variable j for this for loop.
for j in range(len(nums)-1):Now we need to loop through the numbers starting with the length-1, then thorugh the list one less each time. We can do this using the following for loop in python:
for i in range(len(nums)-1-j):When we put the two loops together with indentation, and the if statement and swapping numbers from before, we get the complete python code for the bubble sort algorithm.
for j in range(len(nums)-1):
for i in range(len(nums)-1-j):
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]If you want to check each stage in the example, then try this code that prints each stage.
nums = [7,1,8,4,3,2]
for j in range(len(nums)-1):
for i in range(len(nums)-1-j):
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
print("round=",j+1,nums)Output:
round= 1 [1, 7, 4, 3, 2, 8]
round= 2 [1, 4, 3, 2, 7, 8]
round= 3 [1, 3, 2, 4, 7, 8]
round= 4 [1, 2, 3, 4, 7, 8]
round= 5 [1, 2, 3, 4, 7, 8]
The code can be downloaded and copied from this text file – bubblesort.txt
Is the Bubble sort algorithm efficient?
No the bubble sort is not regarded as an efficient algorithm as we iterate through two loops with a complexity is O(n 2).
We will compare the selection algorithm with the bubble and insertion sorting algorithms in python to see how efficient they are in terms of time. The results will be published in this article below.
Bubble sort questions and answers
What is bubble sort in Python?
Bubble sort is a simple comparison-based sort algorithm in Python. It repeatedly compares adjacent elements and swaps them if they are in the wrong order until the list becomes sorted.
How does bubble sort work?
Bubble sort works by repeatedly scanning the list and swapping adjacent elements if they are out of order. This process continues until the entire list is sorted, with larger elements “bubbling” to the end.
What is the time complexity of bubble sort?
The time complexity of bubble sort is O(n^2) in the average and worst cases. It iterates through the list multiple times, comparing and swapping elements, leading to quadratic time complexity.
When is bubble sort a suitable choice?
Bubble sort is suitable for small datasets or nearly sorted lists. Its simplicity makes it easy to implement and understand, but it becomes inefficient for larger datasets or when more efficient algorithms for sorting are available.
Is Bubble Sort built-in in Python?
No, Bubble Sort is not a built-in sorting method in Python. However, it can be implemented easily using Python’s list operations and control flow statements.
What is Bubble Sort Python?
Bubble Sort Python refers to the implementation of the Bubble Sort algorithm in the Python programming language. It allows users to sort lists or arrays by repeatedly comparing and swapping adjacent elements until the list is sorted in ascending or descending order.
