This article covers the implementation of the Bubble Sort algorithm using the Python programming language.
Bubble Sort is an elementary sorting technique that works by comparing each element with its adjacent neighbor and swapping them if they are out of order.
The sorting process involves multiple iterations, referred to as "passes." Each pass places the next largest element in its correct position. True to its name, the algorithm resembles bubbles as elements "float" to their proper locations through successive comparisons and swaps.
- For a list with n items, the first pass requires comparing (n-1) pairs of items.
- After the first pass, the largest item will be placed in its correct position.
- In the second pass, there will be (n-1) items left, so (n-2) pairs of items need to be compared.
- By the end of the second pass, the second largest item will be positioned correctly.
- This process continues, with each pass sorting the next largest item until the entire list is sorted.
Suppose, our input array/list is: [7, 4, 3, 6, 2]
First Pass
- Given an unsorted list with 5 elements, we have n = 5.
- Therefore, there will be (n-1) = (5-1) = 4 pairs of items that need to be compared.
- During this iteration, the largest element in the list, which is the number 7, will be moved to its correct position.
[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
- With the number 7 already sorted, we are left with (n-1) = (5-1) = 4 elements to sort.
- This means there will be (n-2) = (5-2) = 3 pairs of items to compare in this iteration.
- During this pass, the second largest element, which is the number 6, will be placed in its correct position.
[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
- With the numbers 7 and 6 already sorted, we now have (n-2) = (5-2) = 3 elements left to sort.
- Thus, there will be (n-3) = (5-3) = 2 pairs of items to compare in this iteration.
- During this pass, the third largest element, which is the number 4, will be moved to its correct position.
[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
- With the numbers 7, 6, and 4 already sorted, there are (n-3) = (5-3) = 2 elements remaining to be sorted.
- Therefore, this iteration will involve comparing (n-4) = (5-4) = 1 pair of items.
- In this pass, the fourth largest element, which is the number 3, will be placed in its correct position.
[3, 2, 4, 6, 7] -> [2, 3, 4, 6, 7] – Swap 2 and 3
Fifth Pass
- With the numbers 7, 6, 4, and 3 already sorted, only (n-4) = (5-4) = 1 element remains to be sorted.
- Therefore, there will be (n-5) = (5-5) = 0 pairs of items to compare in this pass. In a list of 5 items, if 4 items are sorted, the remaining 5th item is automatically sorted.
- In this final pass, the fifth largest element (or the smallest element in the list of 5), which is the number 2, will be placed in its correct position without any need for comparison.
[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]
The following example provides a more detailed output of the Bubble Sort implementation. It illustrates the operations occurring 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 O(n^2) .
