Bubble Sort Algorithm with Python using List Example

What is a Bubble Sort?

Bubble Sort is a sorting algorithm used to sort list items in ascending order by comparing two adjacent values. If the first value is higher than the second value, the first value takes the second value’s position, while the second value takes the first value’s position. If the first value is lower than the second value, then no swapping is done.

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 the problem it solves, its optimized form, a step-by-step visual walkthrough, a working Python program, and its performance characteristics.

Implementing the Bubble Sort Algorithm

We will break down 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 values 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:

[3, 6, 9, 21, 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 is 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:

1) Sort complexity

The sort complexity is used to express the amount of execution time 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).

FAQs