Program for Insertion sort (Recursive way) using Python

by | Jun 18, 2021 | Python Programs

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

Program for Insertion sort (Recursive way) using Python

Explanation

Algorithm for Insertion sort:

  1. Iterate through element[1] to element[n-1].
  2. Compare element[i] and put it at suitable index in the array where, 1 <= I <= n-1.
  3. Return the sorted array.

Author

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.