# Insertion sort examples in python - python coding

###### Published at - Sep 09, 2021

In this lesson on python coding, we will talk about one of the Insertion Sort. This algorithm is a very common question for python coding interviews. This article will help if you are preparing for a python coding interview, so let's try to write a simple python program to implement the insertion sort in python.

## Introduction

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

## Time & Space complexity of insertion sort

Worst-case complexity: n^2
Average case complexity: n^2
Best case complexity: n
Space complexity: 1

## Algorithm

To sort an array of size n in ascending order:

1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

## Some Facts about insertion sort

1. Simple implementation: Jon Bentley shows a three-line C version and a five-line optimized version
2. Efficient for (quite) small data sets, much like other quadratic sorting algorithms
3. More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
4. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
5. Stable; i.e., does not change the relative order of elements with equal keys
6. In-place; i.e., only requires a constant amount O(1) of additional memory space Online; i.e., can sort a list as it receives it

## Python example 1

``````def insertion_sort(num_list):
for num in range(1,len(num_list)):
cur_val = num_list[num]
pos = num
while pos > 0 and num_list[pos-1] > cur_val :
num_list[pos] = num_list[pos-1]
pos = pos -1
num_list[pos]= cur_val
return num_list

print insertion_sort([54,26,93,17,77,31,44,55,20])``````

## Python example 2

``````def insertion(s):
for i in range(0,len(s)-1):
if s[i]>s[i+1]:
s[i],s[i+1]=s[i+1],s[i]
for j in range(i,0,-1):
if s[j]<s[j-1]:
s[j],s[j-1]=s[j-1],s[j]
print(s)

insertion([5,2,1,9,0,4,6])``````

## Python example 3

``````def insertionSort(alist):

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

#element to be compared
current = alist[i]

#comparing the current element with the sorted portion and swapping
while i>0 and alist[i-1]>current:
alist[i] = alist[i-1]
i = i-1
alist[i] = current

#print(alist)

return alist

print(insertionSort([5,2,1,9,0,4,6]))``````

All programs will print sorted array as output.

##### Harendra Kanojiya

Hello, I am Harendra Kumar Kanojiya - Owner of this website and a Fullstack web developer. I have expertise in full-stack web development using Angular, PHP, Node JS, Python, Laravel, Codeigniter and, Other web technologies. I also love to write blogs on the latest web technology to keep me and others updated. Thank you for reading the articles.

## Related Posts -

###### Binary search program in py ...

In this lesson on python coding, we will talk about one of the most fam...

###### Hash table program in pytho ...

In this lesson on python coding, we will talk about one of the most fam...

###### Selection sort examples in ...

In this lesson on python coding, we will talk about one of the fundamen...

###### Merge sort explained - pyth ...

In computer science, merge sort is an efficient, general-purpose, and compa...

###### Bubble sort examples in pyt ...

In this lesson on python coding, we will talk about one of the fundamental ...