Question

Write a recursive implementation of insertion sort. Draw a tree of recursive calls for your prototype random dataset and compare its big-O efficiency to that of iterative insertion sort. Run your prototype datasets (best, worst, random) from homework 1 and compare the results to the ones for iterative insertion sort. Which version is better? Make sure to present the results in the table form used in homework 1. Include the data for both iterative and recursive versions.

Answer 1

Solution:

The above picture shows the tree of recursive calls for the dataset - [5,2,9,7,14,8]

//Recursive Java program for insertion sort

import java.util.Arrays;

public class Insertion_Sort  

{

staticvoid insertionSortRecursive(int arr[], int n)

{

// Base case

if (n <= 1)

return;

  

// Sort first n-1 elements

insertionSortRecursive( arr, n-1 );

  

// Insert last element at its correct position in sorted array.

int last = arr[n-1];

int j = n-2;

  

/* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */

while (j >= 0 && arr[j] > last)

{

arr[j+1] = arr[j];

j--;

}

arr[j+1] = last;

}

// Driver Method

public static void main(String[] args)

{

int arr[] = {5, 2, 9, 7, 14, 8};

  

insertionSortRecursive(arr, arr.length);

System.out.println(Arrays.toString(arr));

}

}

The time complexity of both recursive and iterative version is O(n^2).

PLEASE LIKE THE ANSWER IF YOU FIND IT HELPFUL...THANK U.....