Algorithm: Bubble Sort
- FUNCTION: Sorting
- PERFORMANCE: О(n2)
- DESIGN CATEGORY:
- FOUNDED IN: ~1955? (uncertain)
- FOUNDED BY: Anonymous
The way bubble sort works is it starts from the beginning and compares consecutive pairs with each other.
When second number is smaller than the first number they will be swapped. This operation continues all the way to the end of the list causing the largest number to end up in the end.
This iteration will continue until all the numbers are sorted. The name of the algorithm comes from the way it works as large numbers bubble to the end of the list similar to how bubbles bubble to the surface of the water.
You can see a 10 step visual iteration showing how the algorithm swaps the pairs (when condition is satisfied).
STEP BY STEP
You can use the Python code below to create a bubble sort algorithm in your local environment. yield statement is used instead of return to create a generator so that the output is an iterable. (For visualization purposes.)
Bubble sort is not a very efficient sorting algorithm as it’s not suitable for large datasets nor reverse-ordered collections. It will usually perform slower than most of the other sorting algorithms. Only upper-hand of bubble sort is when the collection is already sorted it can be very efficient.
BUBBLE SORT ALGORITHM CODE IN PYTHON
#Bubble Sort Algorithm
def swap(A, p1, p2):
if p1 != p2:
A[p1], A[p2] = A[p2], A[p1]
def bubblesort(lst):
N = len(lst)
if N == 1:
return
for i in range(N - 1):
for j in range(N-1-i):
if lst[j] > lst[j+1]:
swap(lst, j, j+1)
yield lst
BUBBLE SORT ALGORITHM VISUALIZATION
Matplotlib has a great class called animation which can be used to generate animations and live charts as below:
Here is the code to create a matplotlib animation based on the algorithm.
The code is a simplified version that was originally published in Najam Syed’s blog here.
#Visualization Code
import random
import time
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from itertools import count
if __name__ == "__main__":
N = 17
A = [x + 1 for x in range(N)]
random.seed(time.time())
random.shuffle(A)
figure, ax = plt.subplots(figsize=(12,9))
bar_list = ax.bar(range(len(A)), A, width=0.3, align="edge", color="darkgreen")
index=count()
def update_figure(A, bars, iteration):
for bar, value in zip(bars, A):
bar.set_height(value)
anim = animation.FuncAnimation(figure, func=update_figure,
fargs=(bar_list, next(index)), frames=bubblesort(A), interval=100,
repeat=False,save_count=150)
plt.show()If you’re interested in saving your animation as a .gif or video file (such as: .mp4, .mov, .avi), you can check out the Matplotlib Animation saving tutorial here.
HISTORY
Fun Fact:
Former US President Barack Obama mentioned the shortcomings of Bubble Sort algorithm during an interview with the former Google CEO Eric Schmidt. You can watch the amusing interaction and President Obama’s answer below.
Epic exchange occurred on November 14, 2007 in Mountain View, California as
former Google CEO Eric Schmidth asks former US President Barack Obama the best way to sort 1M 32-bit integers to which he replies, probably not the bubble-sort!
