Insertion Sort Algorithm (Python Code)

Algorithm: Insertion Sort

Insertion sort works by taking one item at a time and finding a more suitable location for it. This iteration continues until there is no element to sort.

STEP BY STEP

Insertion Sort in action

Insertion sort is a very simple and basic algorithm and it performs relatively better in comparison to bubble sort and selection sort algorithms.

However, it’s not very efficient in general and so it won’t be suitable for large datasets. 

You can see an illustrated scheme showing how insertion sort algorithm proceeds step by step below.

INSERTION SORT ALGORITHM CODE IN PYTHON

def insertionsort(A):

    for i in range(1, len(A)):
        j = i
        while j > 0 and A[j] < A[j - 1]:
            swap(A, j, j - 1)
            j -= 1
            yield A
            
def swap(A, i, j):
    """Helper function to swap elements i and j of list A."""

    if i != j:
        A[i], A[j] = A[j], A[i]            
            

Matplotlib has a great class called animation which can be used to generate animations and live charts as below:

INSERTION SORT ALGORITHM VISUALIZATION

Visualization of Insertion Sort Algorithm in action (25 items)

Using Python’s animation class and FuncAnimation method you can visualize your sorting algorithm as it sorts a random data you throw at it.

This can be achieved by taking advantage of generators concept in your algorithm and using that iterable generator to create a graph with FuncAnimation. It might seem more complicated that it actually is so feel free to work on the code below.

The code is a simplified version that was originally published in Najam Syed’s blog here.

if __name__ == "__main__":

    N = 25
    A = [x + 1 for x in range(N)]
    random.seed(time.time())
    random.shuffle(A)
    generator = insertionsort(A)

    figure, ax = plt.subplots(figsize=(19,15))
    bar_rects = ax.bar(range(len(A)), A, width=0.3, align="edge", color="green")

    
    iteration = [0]
    def update_figure(A, rects, iteration):
        for rect, val in zip(rects, A):
            rect.set_height(val)
        iteration[0] += 1

        
    anim = animation.FuncAnimation(figure, func=update_figure,
        fargs=(bar_rects, iteration), frames=generator, interval=100,
        repeat=False)
    plt.show()
Collection sorted with Insertion Sort Algorithm

Bubble Sort Algorithm (Python Code)

Algorithm: Bubble Sort

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

Bubble Sort in 10 steps

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:

Bubble Sort Algorithm Visualization (17 items)

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.

List sorted with Bubble Sort Algorithm (55 items)

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!

Merge Sort Algorithm (Python Code)

Algorithm: Merge Sort

Merge sort works by splitting collections to sub-collections until there is one item in the list and then sorts the items as its merging them.

You can see an illustrated scheme showing how merge sort algorithm proceeds step by step below.

STEP BY STEP

Sort Merge step-by-step illustration

You can use the Python code below to create a merge 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.)

Merge sort is generally an efficient algorithm. It’s also a “divide and conquer” algorithm by design since it recursively divides the problem to sublists until these sublists are simple enough to be solved and then merges the solutions to the sublists to end up with one eventual solution to the ultimate problem. (Final sorted list)

MERGE SORT ALGORITHM CODE IN PYTHON

def MergeSort(lst):
    if len(lst) > 1:
        middle = len(lst)//2
        l = lst[:middle]
        r = lst[middle:]
        
        MergeSort(l)
        MergeSort(r)
        
        i,j,k = 0,0,0
        
        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                lst[k]=l[i]
                i+=1
            else:
                lst[k]=r[j]
                j+=1
            k+=1
            
        while i < len(l):
            lst[k]=l[i]
            i+=1
            k+=1
                 
        while j < len(r):
            lst[k]=r[j]
            j+=1
            k+=1
            
    return lst
                
a= MergeSort([2,46,66,3])
print(a)

MERGE SORT ALGORITHM VISUALIZATION

Matplotlib has a great class called animation which can be used to generate animations and live charts as below:

GIF File visualizing Merge Sort Algorithm in action

There is a divine pleasure in watching an algorithm at work. By using Python’s animation library and FuncAnimation method you can visualize your sorting algorithm as it sorts a random data you throw at it.

This can be achieved by taking advantage of generators concept in your algorithm and using that iterable generator to create a graph with FuncAnimation. It might seem more complicated that it actually is so feel free to work on the code below.

This code was originally published by Najam Syed here.

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=MergeSort(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.

Collection sorted with Merge Sort Algorithm

HISTORY

Merge Sort algorithm was invented by John von Neumann in 1945. Neumann was a significant American-Hungarian scientist who also worked with Alan Turing on Artificial Intelligence on scientific and philosophical levels.

He also founded the “Meteorological Program” in Princeton in 1946. Neumann proposed a global warming theory  in 1955, suggesting human activities (burning of coal and oil) on earth might be the cause of global warming which may have changed the atmosphere’s composition sufficiently to account for a general warming of the world by about one degree Fahrenheit.

Another algorithm, called Timsort, is based on merge sort and insertion sort and is used under Python’s hood for its own sorted() function and .sort() methods.

Found by software developer Tim Peters in 2002, Timsort is a hybrid algorithm derived from merge-sort and insertion-sort algorithms.

Tim Peters also wrote The Zen of Python which is embedded in Python as an Easter egg and can be found by running: import this.