Insertion sort in python

Insertion sort is same as selection with some variation. Same like selection sort the list is separated into two parts sorted and unsorted.

Here we add the element to sorted list from unsorted list. The element are not just append or swapped like selection sort. We find the appropriate position for the element then add it to the sorted list.

Algorithm:

1) keep first element as sorted list and others as unsorted list

2) Compare first and second element arrange in order

3) pick next element, compare with all elements before and arrange in order

4) repeat until last element and the list is sorted

Best time complexity: 0[n]

Average time complexity: 0[n^2]

Worst time complexity: 0[n^2]

Working process of selection sort:

Take list [61, 3, 43, 25, 16, 34].

Iteration 1:

 take 61 as sorted list and others as unsorted

 take next element 3 and compare with sorted list

3<61 so swap(the num will be temp placed not fully swapped)

Iteration 2: [3, 61, 43, 25, 16, 34] 

 take 43 and compare with sorted list. Always move from right to left.

43<61 so swap
43<3 no so it is placed in postion 1

Iteration 3: [3, 43, 61, 25, 16, 34]

 take 25 and compare with sorted list.

25<61 so swap
25<43 so swap
25<3 no so it is placed in postion 1

Iteration 3: [3, 25, 43, 61, 16, 34]

 take 16 and compare with sorted list.

16<61 so swap
16<43 so swap
16<25 so swap
16<3 no so the 16 is placed in postion 1

Iteration 4: [3, 16, 25, 43, 61, 34]

 take 34 and compare with sorted list.

34<61 so swap
34<43 so swap
34<25 no
34<16 no
3<16 no 

so the element is placed before 43 in position 3

No element to include in sorted list so the list is sorted
[3, 16, 25, 34, 43, 61]

Code for Insertion sort :

def insertionSort(array):

    for i in range(1, len(array)):

        key = array[i]

        j = i - 1

        

               

        while j >= 0 and key < array[j]:

            array[j + 1] = array[j]

            j = j - 1

        

       

        array[j + 1] = key

list = [9, 5, 1, 4, 3, 43]

print('Before  Sorting:',list)

insertionSort(list)

print('After Sorting:',list)

Output :

Before Sorting: [9, 5, 1, 4, 3, 43] After Sorting: [1, 3, 4, 5, 9, 43]

Hope you understand the program and try yourself for more clear view feel free to comment your thoughts!!