IntKVPair.java
class IntKVPair
{
private int key;
private int value;
IntKVPair(int key, int value)
{
this.key=key;
this.value=value;
}
public int getKey()
{
return this.key;
}
public int getValue()
{
return this.value;
}
}
SortedPositions.java
public class SortedPositions
{
public static void main(String[] args)
{
//Array A initialization
int[] A={4,9,1,5};
//Array of IntKVPair objects
declaration of size of array A
IntKVPair[] arrOfObj=new
IntKVPair[A.length];
//Create object with key as A[i]
and value as i
for(int
i=0;i<A.length;i++)
{
arrOfObj[i]=new
IntKVPair(A[i],i);
}
//Sort arrOfObj using mergesort
which take O(nlogn) time
mergesort(arrOfObj,0,
arrOfObj.length-1);
//Array B contains indices
int[] B=new
int[arrOfObj.length];
//For each element of A
for(int
i=0;i<B.length;i++)
{
//Get index of
element A[i] using binarySearch which take O(logn) time
B[i]=binarySearch(arrOfObj,0,arrOfObj.length,A[i]);
}
//Total time O(nlogn) + O(nlogn) =
O(nlogn)
//Print array B
for(int
i=0;i<B.length;i++)
{
System.out.print(B[i]+" ");
}
}
//This method will return index of key in
arr[]
public static int binarySearch(IntKVPair arr[],int l,
int r, int key)
{
if(l<=r)
{
//middle
int
m=(l+r)/2;
//If key found
return m
if(arr[m].getKey()==key)
{
return m;
}
//If key is
lesser go to left subpart
if(arr[m].getKey()>key)
{
return binarySearch(arr, l,m-1,key);
}
//goto right
subpart
return
binarySearch(arr, m+1,r,key);
}
return -1;
}
//Standard merge sort
public static void mergesort(IntKVPair arr[], int l,
int r)
{
if(l<r)
{
int m =
(l+r)/2;
mergesort(arr,l,m);
mergesort(arr,m+1,r);
merge(arr,l,m,r);
}
}
//Standard merge
public static void merge(IntKVPair arr[], int l, int
m, int r)
{
int n1=m-l+1;
int n2 = r-m;
IntKVPair L[] = new
IntKVPair[n1];
IntKVPair R[] = new
IntKVPair[n1];
for(int i=0;i<n1;i++)
{
L[i] =
arr[l+i];
}
for(int i=0;i<n2;i++)
{
R[i] =
arr[m+i+1];
}
int i=0,j=0;
int k=l;
while(i<n1 &&
j<n2)
{
if(L[i].getKey()<R[j].getKey())
{
arr[k++]=L[i++];
}
else
{
arr[k++]=R[j++];
}
}
while(i<n1)
{
arr[k++]=L[i++];
}
while(j<n2)
{
arr[k++]=R[j++];
}
}
}
Time complexity:
Merge sort will take O(nlogn) time
Binary search will take O(logn) time
Here we are using BinarySearch() for n times to get index of each element of A, So it'll take O(nlogn) time.
Total time = O(nlogn) + O(nlogn) = O(nlogn)
output screenshot:
the programming language is in java Problem 2 You are given an array A with n...
1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1. "Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following: A[M+1]…A[N]A[0]…A[M]. Thus, the "almost sorted"...
Coded in Java. Also advised to use class java.util.HashMap Problem 1 You are given an array A of integers and an integer k. Implement an algorithm that determines, in linear time, the smallest integer that appears at least k times in A. Problem 2 You are given an array A of integers and an integer k. Implement an algorithm that determines in linear time whether there are two distinct indices i and j in the array such that A[i] =...
You are given an array A of integers in sorted order. However, you do not know the length n of the array. Assume that in our programming language arrays are implemented in such a way that you receive an out-of-bounds error message whenever you wish to access an element A[i] with i>n. For simplicity we assume that the error message simply returns the value INT_MAX and that every value in the array is smaller than INT_MAX. (a) Design an algorithm...
1. (16 pts.) Sorted Array Given a sorted array A of n (possibly negative) distinct integers, you want to find out whether there is an index i for which Al = i. Give a divide-and-conquer algorithm that runs in time O(log n). Provide only the main idea and the runtime analysis.
In details explain(the idea in pseudocode) and implement (in java) the following problem: Given a target value and a sorted array, assuming no duplicates in that array, if the target is found in the array, return its index. If not, return where it should be inserted(why it should be inserted there). Give a O(log n) time algorithm. Example: {2,5,8,10}, target=5, returns 1. {2,5,8,10}, target=6, returns 2.
Programming language: Java Home Work No.2 due 09.11.2019 either ascending or descending SORTING: An array is said to be ordered if its values order. In an ascending ordered array, the value of each element is less than or equal to the value of the next element. That is, [each element] <= [next element]. A sort is an algorithm for ordering an array. Of the many different techniques for sorting an array we discuss the bubble sort It requires the swapping...
Design and analysis of algorithms Type in answer Problem 5. Given a sorted array of distinct integers A[1- -n], you want to find out whether there is an index I for which Ai-i. Give a divide-and-conquer algorithm that runs in time O(log n)
Need help with my Java Hw: Consider an algorithm that sorts an array of n elements by finding the smallest and largest elements and then exchanges those elements with the elements in the first and last positions in the array. Then the size of the array is reduced by two elements after excluding the two elements that are already in the proper positions, and the process is repeated on the remaining part of the array until the entire array is...
I need help In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is not limited to finding only the median, but can generally find the ith element with 0≤i <n. Implement this generic version of the median algorithm by creating a class selector in the ads.set2.select package and implementing the following method: /** * Returns the...
Selection Sort is a common algorithm to sort the elements of an array. First, it scans the elements of the array to find the smallest value and places it at index 0, thus creating a sorted “subarray” of size 1 that contains the smallest value. Then it scans the remaining unsorted values for the new smallest value and places it at index 1, creating a sorted subarray of size 2 that contains the 2 smallest values. It continues in this...