Table of Contents
Introduction
In the previous article we understood how insertion sort work. Now we will discuss the recursive way to implement insertion sort in our program.
Program
def sort(ip_arr, length):
if length <= 1:
return
sort(ip_arr, length - 1)
end_ele = ip_arr[length - 1]
j = length - 2
while(j>=0 and ip_arr[j] > end_ele):
ip_arr[j+1] = ip_arr[j]
j = j - 1
ip_arr[j + 1] = end_ele
ip_arr = [6, 5, 11, 101, 13]
print("The input array is: ", ip_arr)
sort(ip_arr, len(ip_arr))
print("The sorted array is :")
for i in range(len(ip_arr)):
print(ip_arr[i])
Output
Explanation
Algorithm for Insertion sort:
- Iterate through element[1] to element[n-1].
- Compare element[i] and put it at suitable index in the array where, 1 <= I <= n-1.
- Return the sorted array.
0 Comments