Bubble Sort Algorithm with Python using List Example

This process is repeated until all the values in a list have been compared and swapped if necessary. Each iteration is usually called a pass. The number of passes in a bubble sort is equal to the number of elements in a list minus one.

In this Bubble Sorting in Python tutorial you will learn:

• What is a Bubble Sort?
• Implementing the Bubble Sort Algorithm
• Optimized Bubble Sort Algorithm
• Visual Representation
• Python Examples
• Code Explanation
• Bubble sort advantages
• Bubble sort Disadvantages
• Complexity Analysis of Bubble Sort

Implementing the Bubble Sort Algorithm

We will breakdown the implementation into three (3) steps, namely the problem, the solution, and the algorithm that we can use to write code for any language.

The problem

A list of items is given in random order, and we would like to arrange the items in an orderly manner

Consider the following list:

[21,6,9,33,3]

The solution

Iterate through the list comparing two adjacent elements and swapping them if the first value is higher than the second value.

The result should be as follows:

[3,6,9,21,33]

Algorithm

The bubble sort algorithm works as follows

Step 1) Get the total number of elements. Get the total number of items in the given list

Step 2) Determine the number of outer passes (n - 1) to be done. Its length is list minus one

Step 3) Perform inner passes (n - 1) times for outer pass 1. Get the first element value and compare it with the second value. If the second value is less than the first value, then swap the positions

Step 4) Repeat step 3 passes until you reach the outer pass (n - 1). Get the next element in the list then repeat the process that was performed in step 3 until all the values have been placed in their correct ascending order.

Step 5) Return the result when all passes have been done. Return the results of the sorted list

Step 6) Optimize Algorithm

Avoid unnecessary inner passes if the list or adjacent values are already sorted. For example, if the provided list already contains elements that have been sorted in ascending order, then we can break the loop early.

Optimized Bubble Sort Algorithm

By default, the algorithm for bubble sort in Python compares all items in the list regardless of whether the list is already sorted or not. If the given list is already sorted, comparing all values is a waste of time and resources.

Optimizing the bubble sort helps us to avoid unnecessary iterations and save time and resources.

For example, if the first and second items are already sorted, then there is no need to iterate through the rest of the values. The iteration is terminated, and the next one is initiated until the process is completed as shown in the below Bubble Sort example.

Optimization is done using the following steps

Step 1) Create a flag variable that monitors if any swapping has occurred in the inner loop

Step 2) If the values have swapped positions, continue to the next iteration

Step 3) If the benefits have not swapped positions, terminate the inner loop, and continue with the outer loop.

An optimized bubble sort is more efficient as it only executes the necessary steps and skips those that are not required.

Visual Representation

Given a list of five elements, the following images illustrate how the bubble sort iterates through the values when sorting them

The following image shows the unsorted list

First Iteration

Step 1)

The values 21 and 6 are compared to check which one is greater than the other.

21 is greater than 6, so 21 takes the position occupied by 6 while 6 takes the position that was occupied by 21

Our modified list now looks like the one above.

Step 2)

The values 21 and 9 are compared.

21 is greater than 9, so we swap the positions of 21 and 9

The new list is now as above

Step 3)

The values 21 and 33 are compared to find the greater one.

The value 33 is greater than 21, so no swapping takes place.

Step 4)

The values 33 and 3 are compared to find the greater one.

The value 33 is greater than 3, so we swap their positions.

The sorted list at the end of the first iteration is like the one above

Second Iteration

The new list after the second iteration is as follows

Third Iteration

The new list after the third iteration is as follows

Fourth Iteration

The new list after the fourth iteration is as follows

Python Examples

The following code shows how to implement the Bubble Sort algorithm in Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Executing the above bubble sort program in Python produces the following results

[6, 9, 21, 3, 33]

Code Explanation

The explanation for the Python Bubble Sort program code is as follows

HERE,

1. Defines a function bubbleSort that accepts a parameter theSeq. The code does not output anything.
2. Gets the length of the array and assigns the value to a variable n. The code does not output anything
3. Starts a for loop that runs the bubble sort algorithm (n – 1) times. This is the outer loop. The code does not output anything
4. Defines a flag variable that will be used to determine if a swap has occurred or not. This is for optimization purposes. The code does not output anything
5. Starts the inner loop that compares all the values in the list from the first to the last one. The code does not output anything.
6. Uses the if statement to check if the value on the left-hand side is greater than the one on the immediate right side. The code does not output anything.
7. Assigns the value of theSeq[j] to a temporal variable tmp if the condition evaluates to true. The code does not output anything
8. The value of theSeq[j + 1] is assigned to the position of theSeq[j]. The code does not output anything
9. The value of the variable tmp is assigned to position theSeq[j + 1]. The code does not output anything
10. The flag variable is assigned the value 1 to indicate that a swap has taken place. The code does not output anything
11. Uses an if statement to check if the value of the variable flag is 0. The code does not output anything
12. If the value is 0, then we call the break statement that steps out of the inner loop.
13. Returns the value of theSeq after it has been sorted. The code outputs the sorted list.
14. Defines a variable el that contains a list of random numbers. The code does not output anything.
15. Assigns the value of the function bubbleSort to a variable result.
16. Prints the value of the variable result.

Bubble sort advantages

The following are some of the advantages of the bubble sort algorithm

• It is easy to understand
• It performs very well when the list is already or almost sorted
• It does not require extensive memory.
• It is easy to write the code for the algorithm
• The space requirements are minimal compared to other sorting algorithms.

Bubble sort Disadvantages

The following are some of the disadvantages of the bubble sort algorithm

• It does not perform well when sorting large lists. It takes too much time and resources.
• It's mostly used for academic purposes and not the real-world application.
• The number of steps required to sort the list is of the order n²

Complexity Analysis of Bubble Sort

There are three types of Complexity are:

1) Sort complexity

The sort complexity is used to express the amount of execution times and space that it takes to sort the list. The bubble sort makes (n – 1) iterations to sort the list where n is the total number of elements in the list.

2) Time complexity

The time complexity of the bubble sort is O(n²)

The time complexities can be categorized as:

• Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as [Big-O] O(n²)
• Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as [Big-Omega] Ω(n)
• Average case – this occurs when the list is in random order. The average Complexity is represented as [Big-theta] ⊝(n²)

3) Space complexity

The space complexity measures the amount of extra space that is needed for sorting the list. The bubble sort only requires one (1) extra space for the temporal variable used for swapping values. Therefore, it has a space complexity of O (1).

Summary

• The bubble sort algorithm works by comparing two adjacent values and swapping them if the value on the left is less than the value on the right.
• Implementing a bubble sort algorithm is relatively straight forward with Python. All you need to use are for loops and if statements.
• The problem that the bubble sort algorithm solves is taking a random list of items and turning it into an ordered list.
• The bubble sort algorithm in data structure performs best when the list is already sorted as it performs a minimal number of iterations.
• The bubble sort algorithm does not perform well when the list is in reverse order.
• The bubbler sort has a time complexity of O (n²) and a space complexity of O (1)
• The bubbler sort algorithm is best suited for academic purposes and not real-world applications.
• The optimized bubble sort makes the algorithm more efficient by skipping unnecessary iterations when checking values that have already been sorted.