Tuesday, 27 June 2017

Python - Insertion Sort Algorithm Implementation

Insertion sort algorithm - In the last couple of articles, we studied Bubble sort and Selection sort algorithms. In this article, we will learn about another sorting algorithm - Insertion sort. Just like Bubble sort and selection sort, time complexity of this algorithm is O(n^2) and space complexity being O(1).


Selection Sort Algorithm


1. First element i.e. element at index 0 is always sorted and is the part of sorted sub-list
2. Select next element
3. Compare it with all elements in sorted sub-list
4. If the value of the element is smaller, swap it with the element(s) in sorted sub-list
5. Continue till we get an element from sorted sub-list which is smaller than the element
6. Insert the element in the sorted sub-list
7. Get the next element
7. Repeat this process for selected element

Example


Consider the following list-


Initially, the first element in the list is already sorted. Hence we add that to sorted sub-list identified with green color.


Iteration 1:
Compare element at index 1 with the elements in sorted sub-list and insert at appropriate location. Here, array[0] > array[1], so array[1] should appear before array[0]. Hence we swap them to adjust their positions.


Iteration 2:
In this case, array[2] > array[1], hence nothing needs to be required as it is already at appropriate position.


Iteration 3:
In this case, array[3] < array[2], so we swap them so that array[3]=7 and array[2]=1. Now, array[2] which is 1 is again less than array[1], so we swap them again such that array[1]=1 and array[2]=5. Now also, array[1] > array[0], so we swap these elements such that array[0]=1 and array[1]=3 and we are done.


Iteration 4:


Iteration 5:


Iteration 6:


Iteration 7:


Python Implementation:


def insertion_sort(array):
    
    n = len(array)
    
    for i in range(1, n):
        j = i
        current = array[j]
        while j > 0 and array[j-1] > current:
            array[j] = array[j-1]
            j -= 1
        array[j] = current
        

my_array = [5, 3, 7, 1,4, 8, 2, 6]
insertion_sort(my_array)
print my_array

Output:

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

0 comments:

Post a Comment