Python Tutorial

# 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 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]
```

Python Tutorial

## Python installation

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

^