

In [1]:

    
import ipytracer
from IPython.display import display

Insertion Sort (Insert Sort)

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Complexity

Time

Worst-case: $O(n^2)$
Bast-case: $O(n)$
Average: $O(n^2)$

Reference

Wikipedea

Code1 - List1DTracer



In [6]:

    
def insertion_sort(unsorted_list):
    x = ipytracer.List1DTracer(unsorted_list)
    display(x)
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1]  = x[j]
            j = j - 1
        x[j+1] = key
    return x.data

work



In [7]:

    
insertion_sort([6,4,7,9,3,5,1,8,2])









    Out[7]:





[1, 2, 3, 4, 5, 6, 7, 8, 9]

Code2 - ChartTracer



In [8]:

    
def insertion_sort(unsorted_list):
    x = ipytracer.ChartTracer(unsorted_list)
    display(x)
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1]  = x[j]
            j = j - 1
        x[j+1] = key
    return x.data

work



In [9]:

    
insertion_sort([6,4,7,9,3,5,1,8,2])









    Out[9]:





[1, 2, 3, 4, 5, 6, 7, 8, 9]