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.

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.

Worst-case complexity: n^2

Average case complexity: n^2

Best case complexity: n

Space complexity: 1

To sort an array of size n in ascending order:

- Iterate from arr[1] to arr[n] over the array.
- Compare the current element (key) to its predecessor.
- 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.

- Simple implementation: Jon Bentley shows a three-line C version and a five-line optimized version
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
- 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
- Stable; i.e., does not change the relative order of elements with equal keys
- 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

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

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

```
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.

python
python basic programs
python coding
python interview questions
python programming
python tutor

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

Quicksort is an in-place sorting algorithm. Developed by British computer s...

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

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

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

Follow us on facebook Click Here

Scan from mobile

Scan from mobile