# Write a Program to implement Insertion sort

0 like 0 dislike
245 views

recategorized
Write a Program to implement Insertion sort
 Where can I do online courses From Word's Top Instructors? UDEMY:: Attend All Udemy Courses in Just INR 450[Coupon] Coursera:: Join For FREE

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

## Ques. Write a Program to implement Insertion sort

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.

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

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