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 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

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()