Bubble Sort implementation in Python [Data Structures & Algorithms]

Facebook Tweet LinkedIn Pin Print EmailShares

This article deals with implementing Bubble Sort algorithm using Python programming language.

Bubble Sort is a simple sorting algorithm that compares each element in the list with its adjacent element and sort that pair of elements if they are not in order.

There can be multiple iterations while sorting. Each iteration can be named as “Pass“. So, there can be the first pass, second pass, and so on. Each pass will put/place the next largest value in its proper place. As in the name of this sorting algorithm, each element behaves like a “bubble“. It will jump to its proper location like a bubble.

If there are n items in the list then there will be (n-1) pairs of items that need to be compared in the first pass.
After the first pass, the largest element of the list will be placed in its proper place.
Now, in the second pass, there will be (n-1) items left for sorting. This means that there will be (n-2) pairs of items that need to be compared in the second pass.
In the second pass, the second largest element of the list will be placed in its proper place.
In this way, other elements of the list are sorted.

Suppose, our input array/list is: [7, 4, 3, 6, 2]

First Pass

There are 5 elements in the unsorted list. Hence, n = 5.
So, there will be (n-1) = (5-1) = 4 pairs of items to be compared.
In this iteration, the largest element of the list, i.e. number 7 will be sorted to its proper place.

[7, 4, 3, 6, 2] -> [4, 7, 3, 6, 2] – Swap 4 and 7
[4, 7, 3, 6, 2] -> [4, 3, 7, 6, 2] – Swap 3 and 7
[4, 3, 7, 6, 2] -> [4, 3, 6, 7, 2] – Swap 6 and 7
[4, 3, 6, 7, 2] -> [4, 3, 6, 2, 7] – Swap 2 and 7

Second Pass

As number 7 (1 element) is already sorted, we have (n-1) = (5-1) = 4 elements remaining to sort.
So, there will be (n-2) = (5-2) = 3 pairs of items to be compared.
In this iteration, the second largest element of the list, i.e. number 6 will be sorted to its proper place.

[4, 3, 6, 2, 7] -> [3, 4, 6, 2, 7] – Swap 4 and 3
[3, 4, 6, 2, 7] -> [3, 4, 6, 2, 7] – No Swap as 4 & 6 are already sorted
[3, 4, 6, 2, 7] -> [3, 4, 2, 6, 7] – Swap 6 and 2

Third Pass

As number 7 & 6 (2 elements) are already sorted, we have (n-2) = (5-2) = 3 elements remaining to sort.
So, there will be (n-3) = (5-3) = 2 pairs of items to be compared.
In this iteration, the third largest element of the list, i.e. number 4 will be sorted to its proper place.

[3, 4, 2, 6, 7] -> [3, 4, 2, 6, 7] – No Swap
[3, 4, 2, 6, 7] -> [3, 2, 4, 6, 7] – Swap 4 and 2

Fourth Pass

As number 7, 6, & 4 (3 elements) are already sorted, we have (n-3) = (5-3) = 2 elements remaining to sort.
So, there will be (n-4) = (5-4) = 1 pair of items to be compared.
In this iteration, the fourth largest element of the list, i.e. number 3 will be sorted to its proper place.

[3, 2, 4, 6, 7] -> [2, 3, 4, 6, 7] – Swap 2 and 3

Fifth Pass

As number 7, 6, 4, & 3 (4 elements) are already sorted, we have (n-4) = (5-4) = 1 element remaining to sort.
So, there will be (n-5) = (5-5) = 0 pair of items to be compared. Because, in a list of 5 items, if 4 items are sorted then the 5th (last) item gets sorted automatically.
In this iteration, the fifth largest element of the list (or the smallest element in the list of 5 elements), i.e. number 2 will be automatically sorted to its proper place. So, no comparison is required.

[2, 3, 4, 6, 7] – Nothing to Swap. Sorting completed.

Implementation in Python

Below is the Bubble Sort implementation in Python.


def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                # sorting by using simultaneous assignments in python
                arr[j], arr[j+1] = arr[j+1], arr[j]


arr = [7, 4, 3, 6, 2]
print ('Before sorting: {}'.format(arr))
bubble_sort(arr)
print ('After sorting: {}'.format(arr))

# Output: 
# Before sorting: [7, 4, 3, 6, 2]
# After sorting: [2, 3, 4, 6, 7]

Below is the same implementation as above but with a more verbose output. This shows what’s happening in each iteration of the sorting process.


def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        print (arr)
        for j in range(n-i-1):          
            if arr[j] > arr[j+1]:
                # sorting by using simultaneous assignments in python
                arr[j], arr[j+1] = arr[j+1], arr[j]             
                print ('-- {} - Swap {} and {}'.format(arr, arr[j+1], arr[j]))
            else:
                print ('-- {} - No Swap'.format(arr))


arr = [7, 4, 3, 6, 2]
bubble_sort(arr)


'''
Output: 
[7, 4, 3, 6, 2]
-- [4, 7, 3, 6, 2] - Sort 4 and 7
-- [4, 3, 7, 6, 2] - Sort 3 and 7
-- [4, 3, 6, 7, 2] - Sort 6 and 7
-- [4, 3, 6, 2, 7] - Sort 2 and 7
[4, 3, 6, 2, 7]
-- [3, 4, 6, 2, 7] - Sort 3 and 4
-- [3, 4, 6, 2, 7] - No Sort
-- [3, 4, 2, 6, 7] - Sort 2 and 6
[3, 4, 2, 6, 7]
-- [3, 4, 2, 6, 7] - No Sort
-- [3, 2, 4, 6, 7] - Sort 2 and 4
[3, 2, 4, 6, 7]
-- [2, 3, 4, 6, 7] - Sort 2 and 3
[2, 3, 4, 6, 7]
'''

Time Complexity

The time complexity of Bubble Sort is $latex O(n^2) $.

Hope this helps. Thanks.

Implementation in Python

Related posts: