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 JECRC University CSE-III Sem Data Structure and Algorithm Lab Experiments CLICK HERE
| 
| 
