**Ques. Write a Program to implement Insertion sort**

**Answer : **

**Insertion sort : **It is an sorting algorithm in which first element in the array is assumed as sorted, even if it is an unsorted . then, each element in the array is checked with the previous elements, resulting in a growing sorted output list. With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted.

**Advantage : **

- It is more efficient than other similar algorithms such as bubble sort or selection sort.
- It is simple to implement and is quite efficient for small sets of data.

**Disadvantage :**

- an insertion sort is less efficient on larger data sets and less efficient than the heap sort or quick sort algorithms.

**Algorithm : **

for j=2 to a.length

key = a[j]

insert a[j] into sorted sequence a[1.........j-1]

i = j - 1

while i > 0 and a[i] > key

a[i + 1] = a[i]

i = i - 1

a[i + 1] = key

**For eg : [ 13**, 12, 14, 5, 6 ]

Let 's loop for i = 1 to 4

i = 1. as 12 is smaller than 13, move 13 and insert 12 before 13

**[12, 13**, 14, 5, 6 ]

i = 2. 14 will remain at same location as all elements in A[0..I-1] are smaller than 14

**[12, 13, 14**, 5, 6]

i = 3. 5 will move at beginning and other elements from 12 to 14 will move one position to front from their current location.

**[5, 12, 13, 14**, 6]

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position to front of their current position.

**[5, 6, 12, 13, 14]**

**Program : **

a=[5, 6, 12, 13, 14]

b=[]

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

key = a[i]

j = i-1

while j>0 and a[j-1]>key:

a[j+1]=a[j]

j = j-1

a[j+1] = key

print("elements in sorted order are ")

for i in a:

b.append(i)

print(b)

**Output :**

elements in sorted order are

[5, 6, 12, 13, 14]

**For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments **** CLICK HERE**