Activity # 1: Apply insertion sort & Binary Search We know that we must have a s
ID: 3738085 • Letter: A
Question
Activity # 1: Apply insertion sort & Binary Search We know that we must have a sorted list in order to utilize Binary Search. Write out the application of Insertion Sort (in step-by-step format) to each of the 3 unsorted arrays of integers. Then apply Binary Search (in step-by-step format) on the now-sorted arrays to locate the given target. Don't worry about including your solutions as part of your submission Target 3; Array [9, 6, 4, 3, 0, 10, -2) Target 1; Array 7, 8, 4, 4, 10, 25) Target 17; Array (1, 2, 3, 4, 0, 17, 8, 9, -5, 10Explanation / Answer
/*If you have any query do comment in the comment section*/
Applications of Insertion Sort:
1) Very much efficient for sorting small lists say for 20 elements.
2) Helpful in sorting almost sorted array.
import java.util.*;
public class InsertionSort
{
public static void main(String[]args)
{
int arr1[]= {9,6,4,3,0,10,-2};
int arr2[]= {7,8,4,4,10,25};
int arr3[]= {1,2,3,4,0,17,8,9,-5,10};
int target1=3,target2=1,target3=17;
InsertionSort(arr1,7);
InsertionSort(arr2,6);
InsertionSort(arr3,10);
int res1=binarySearch(arr1,0,6,target1);
int res2=binarySearch(arr2,0,5,target2);
int res3=binarySearch(arr1,0,9,target3);
if(res1==-1)
System.out.println("Target1 not found");
else
{
System.out.println("Target1 found at : "+res1);
}
if(res2==-1)
System.out.println("Target2 not found");
else
{
System.out.println("Target2 found at : "+res2);
}
if(res3==-1)
System.out.println("Target3 not found");
else
{
System.out.println("Target3 found at : "+res3);
}
}
public static int binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
public static void InsertionSort(int arr[],int len)
{
for (int i=1; i<len; ++i)
{
int key = arr[i];
int j = i-1;
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.