This is my 45th day of #100DaysOfcode and #python learning. I Continued to learned more about algorithm. Today I learned Insertion sort along with time complexity and space complexity.

Insertion sort is the simple sorting algorithm. We start with element at index 1 as the key. We compare the key element with the element before it at first step with the element at index 0. We continue this process until the list is sorted.

Insertion Sort

Insertion sort is simple sorting technique. It works similar to the way we sort playing card in our hands. The array is virtually split into a sorted.

def InsertionSort(B):
    for i in range(1,len(B)):
        key = B[i]
        j = i - 1
        while j >= 0 and key < B[j]:
            B[j + 1] = B[j]
            j -= 1
        B[j + 1] = key
        print(f'current array is{B}.')

B = [12,3,34,13,4]
InsertionSort(B)
print('Sorted array is:')
for i in range(len(B)):
    print('%d'%B[i])

Step1

Take element 3 as key element than compare it with element to the left i.e with 12. Here 3 is smaller than 12 so inserted 3 before 12. Now new element is
3 12 34 13 4

Step2

Here we take 34 as a key now compare it with 12. 12 is smaller than 34 so we don't need to insert their position. New array is
3 12 34 13 4

Step3

Now take 13 as a key element. Now comparing 34 and 13 we found that 13 is smaller than 34 so we inserted 13 before 34. Also compare 13 and 12 we found 12 is smaller than 13 so now 13 is in correct position. New array is,
3 12 13 34 4

Step4

Take 4 as a key and compare it with 34. Here 4 is smaller than 34 so inserted it before 34 again 4 is smaller than 13 inserted it before 13 also 4 is smaller than 12 inserted it before 12. Now 4 is in correct position. Our optimal sorted list is,
3 4 12 13 34

When above code is run we can get,

current array is[3, 12, 34, 13, 4].
current array is[3, 12, 34, 13, 4].
current array is[3, 12, 13, 34, 4].
current array is[3, 4, 12, 13, 34].
Sorted array is:
3
4
12
13
34

Day 45 Of #100DaysOfCode and #Python
* More About Algorithm
* Insertion Sort
* Best Case Time Complexity(Big-omega)O(n)
* Worst Case Time Complexity(Big-O)O(n*2)
* Space complexity O(n)#WomenWhoCode #100daysofcode #CodeNewbie #beginner #womenintech #Python #DEVCommunity pic.twitter.com/tHYbm81zuk

— Durga Pokharel (@mathdurga) February 7, 2021