Bubble Sort is the simplest sorting algorithm. It works by changing positions in the adjacent elements if they are in the wrong order.
Basic Example
Assume we have the following list of integers:
(32, 5, 12, 9, 72)
With bubble sort, we will traverse through the list and compare the adjacent elements, as many times it is needed until we will find that there are no elements that need to swap positions.
First Pass
(32, 5, 12, 9, 72) => (5, 32, 12, 9, 72 ) : Swaps the first two elements (32>5)
(5, 32, 12, 9, 72 ) => (5, 12, 32, 9, 72) : Swaps second and third element (32>12)
(5, 12, 32, 9, 72) => (5,12, 9, 32, 72) : Swaps second and third element (32>9)
(5, 12, 9, 32, 72) => (5, 12, 9, 32, 72) : Does not swap since items are ordered already
Second Pass
(5, 12, 9, 32, 72) => (5, 12, 9, 32, 72) : Does not swap since items are ordered already
(5, 12, 9, 32, 72) => (5, 9, 12, 32, 72) : Swaps second and third element (12>9)
(5, 9, 12, 32, 72) => (5, 9, 12, 32, 72) : Does not swap since items are ordered already
(5, 9, 12, 32, 72) => (5, 9, 12, 32, 72) : Does not swap since items are ordered already
The list is now sorted but bubble sort algorithm does not know that. It will perform one more pass and as soon as it finds out that there are no further swaps needed it will know that the list is sorted
Third Pass
(5, 9, 12, 32, 72) => (5, 9, 12, 32, 72) : Does not swap
(5, 9, 12, 32, 72) => (5, 9, 12, 32, 72) : Does not swap
(5, 9, 12, 32, 72) => (5, 9, 12, 32, 72) : Does not swap
(5,9, 12, 32, 72) => (5, 9, 12, 32, 72) : Does not swap
Python Implementation
def bubble_sort(elements):
elements_length = len(elements)
# Loop through all elements - essentially the passes
for item in range(elements_length):
# Loop the list from 0 to item-i-1
for i in range(0, elements_length-item-1):
# Swap if the element found is greater
# than the next element
if elements[i] > elements[i+1] :
elements[i], elements[i+1] = elements[i+1], elements[i]
a = [5,2,123,6,900,23]
print(a) # [5, 2, 123, 6, 900, 23]
bubble_sort(a)
print(a) # [2, 5, 6, 123, 23, 900]The outer loop represents essentially the times we will pass to check for unordered elements. The inner loop checks within the list if the current element is bigger than the next element. If yes then it swaps their position.
This will perform several unmercenary passes since it loops without checking if the code has performed any swaps. Remember that if there are no swaps performed that means that the list is sorted.
Optimization
We can easily avoid unnecessary loops and thus save time and resources by simply add a control to check if any swaps took place in the inner loop.
def bubble_sort(elements):
elements_length = len(elements)
# Loop through all elements - essentially the passes
for item in range(elements_length):
# Add control
swapped = False
# Loop the list from 0 to item-i-1
for i in range(0, elements_length-item-1):
# Swap if the element found is greater
# than the next element
if elements[i] > elements[i+1] :
elements[i], elements[i+1] = elements[i+1], elements[i]
# Change the value of control since we had a swap
# and we need to recheck if there are more to do
swapped = True
# If there were no element swapped
# by inner loop, then stop the execution
if swapped == False:
break
a = [5,2,123,6,900,23]
print(a) # [5, 2, 123, 6, 900, 23]
bubble_sort(a)
print(a) # [2, 5, 6, 123, 23, 900]Comparison with and without optimization
Below we have the same code as above, just combined in one file and adding at the end of it a time measurement. Also, we have added some more elements in the list to sort to make the difference more clear.
from timeit import default_timer as timer
from datetime import timedelta
def bubble_sort(elements):
elements_length = len(elements)
# Loop through all elements - essentially the passes
for item in range(elements_length):
# Loop the list from 0 to item-i-1
for i in range(0, elements_length-item-1):
# Swap if the element found is greater
# than the next element
if elements[i] > elements[i+1] :
elements[i], elements[i+1] = elements[i+1], elements[i]
# Change the value of control since we had a swap
# and we need to recheck if there are more to do
def bubble_sort_optimized(elements):
elements_length = len(elements)
# Loop through all elements - essentially the passes
for item in range(elements_length):
# Add control
swapped = False
# Loop the list from 0 to item-i-1
for i in range(0, elements_length-item-1):
# Swap if the element found is greater
# than the next element
if elements[i] > elements[i+1] :
elements[i], elements[i+1] = elements[i+1], elements[i]
# Change the value of control since we had a swap
# and we need to recheck if there are more to do
swapped = True
# If there were no element swapped
# by inner loop, then stop the execution
if swapped == False:
break
a = [5,2,123,6,900,23,1,6,234,123,0]
timer_start = timer()
bubble_sort(a)
timer_end = timer()
print(timedelta(minutes=timer_end-timer_start))
timer_start = timer()
bubble_sort_optimized(a)
timer_end = timer()
print(timedelta(minutes=timer_end-timer_start))The outcome of those print statements is:
0:00:00.001038 0:00:00.000408
The not optimized function needs more than double the time than the optimized one.
Bubble sort has several advantages. It is simple to write, needs a few lines of code and it is easy to understand. The biggest issue we have with bubble sort is that the time it takes to execute increases exponentially for each number we add to the list we want to sort.