Python Program for Insertion Sort

What is insertion sort ?

One element from the list of elements is consumed in each iteration to find its correct position.
i'th iteration we "insert" the i'th element array[i] into it's correct position among array[1], array[2], ... array[i-1] which were previously placed in sorted order.

Insertion Sorting Steps

insertion sorting

Insertion Sorting Time complexity

Insertion sorting time complexity is O(N^2). here N is the number of elements in the list.

Insertion Sort Python Program

#!/usr/bin/python                                                               
                                                                                
def insertion_sort (list_vals):                                                 
    num_of_elements = len(list_vals);                                           
    for i in range(0, num_of_elements):                                         
        # temp stores current element whose left side is traversed              
        # to find correct position                                              
        temp = list_vals[i];                                                    
        j = i;                                                                  
        # checks whether left side elements are less than current element.      
        while(j > 0 and temp < list_vals[j-1]):                                 
            list_vals[j] = list_vals[j-1];                                      
            j = j - 1;                                                          
                                                                                
        # moving current element to correct position in left side.              
        list_vals[j] = temp;                                                    
    return list_vals;                                                           
                                                                                
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [30, 10, 20, 70, 60, 80, 50, 40];                               
    print("Collection before sorting: %s" % str(list_vals));                    
    print("Sorted list elements: %s" % str(insertion_sort(list_vals)));                                                                                                                                             
Output:
$ python insertion_sort.py 
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]


Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^