Using Java Problem-1 Let A and B two arrays of n elements, each. Given a number
ID: 3726917 • Letter: U
Question
Using Java
Problem-1
Let A and B two arrays of n elements, each. Given a number K, give an O(nlogn) time algorithm for determining whether there exists a A and b B suck that a + b = K.
Hints:
Use Heapsort(A, n)
Take Advantage of BinarySearch()
Problem-2
Among Quicksort, Selection sort, Insertion sort and Heap sorts which one needs the minimum number of swaps?
Hints:
Go over the class lecture for individual sorting and simulate with an array.
Problem-3
There are two sorted arrays A and B. First one is of size m + n containing m elements and another one is of size n and containing n elements. Merge these two arrays into the first array of size m + n such that the output is sorted.
Hints:
Trick is to start filling the destination array from the back with the largest elements.
Problem-4
Given an array A of n elements. Find three elements i, j and k in the array such that A[i]2 + A[j]2 = A[k]2.
Hints:
Use Heapsort(A, n)
For each array index i compute A[i]2 and store in array
Search for two numbers in array from 0 to i-1 which adds to A[i].
Explanation / Answer
Please find my answer for Q1.
Since you have not posted HeapSort(), So I used quick sort.
public class HasElements
{
static boolean hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
int l, r;
/* Sort the elements */
sort(A, 0, arr_size-1);
/* Now look for the two candidates
in the sorted array*/
l = 0;
r = arr_size-1;
while (l < r)
{
if(A[l] + A[r] == sum)
return true;
else if(A[l] + A[r] < sum)
l++;
else // A[i] + A[j] > sum
r--;
}
return false;
}
/* Below functions are only to sort the
array using QuickSort */
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int arr[], int low, int high)
{
int pivot = arr[high];
// index of smaller element
int i = (low-1);
for (int j=low; j<=high-1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that
implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
//main function
public static void main(String args[])
{
int A[] = {1, 4, 45, 6, 10, -8};
int n = 16;
int arr_size = 6;
if( hasArrayTwoCandidates(A, arr_size, n))
System.out.println("Array has two "+
"elements with given sum");
else
System.out.println("Array doesn't have "+
"two elements with given sum");
}
}
Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.