I don\'t know what I am doing wrong in differnce.java. Please explain At very en

Question

I don't know what I am doing wrong in differnce.java. Please explain

At very end write the code for difference.java Solve the problem with first quick sort then create method in DifferencePairs.java to calculate the difference paris.

Problem: Given an array of integers find all pairs of integers, a and b, where a – b is equal to a given number. For example, consider the following array and suppose we want to find all pairs of integers a and b where a – b = 3 A = [10, 4, 6, 16, 1, 6, 12, 13] Then your method should return the following pairs (Each pair should be printed in a separate line): 4, 1 15, 12 13, 10 A poor solution: There are several solutions to this problem. The most straightforward (but inefficient) solution is to set up a nested loop structure that goes over the elements of the array one by one and for each element performs a sequential search on the entire array. The running time for this algorithm is quadratic due to the nested loop structure and the sequential search for each array element. What you need to do for this assignment When the size of the array is very large then the quadratic algorithm may be too slow to be useful. There are a number of strategies that can be employed to reduce the running time, and at this point we have covered enough topics to design a more efficient algorithm. Based on the material covered thus far in this course, design and implement a more efficient algorithm for this problem. Hint: You might find it helpful to first sort the array using quicksort. Your algorithm must on average have a running time of O(nlogn) where n is the number of elements in the array. The framework for your algorithm should satisfy the following criteria: 1. I have created a class Pair.java which stores a pair of integers. You need to add this class to your project. 2. Create a class called DifferencePairs, to contain your algorithm and associated methods and attributes. 3. In your DifferencePairs class, encapsulate your algorithm within a method called findPairs, with the signature: public Pair[] findPairs(int array[], int diff) 4. The value returned by your findPairs method should be an array of Pair, where the difference between the first element and the second element in each pair in the array is equal to diff. If no such pair is found, then your method should return null. 5. You may use the codes from the textbook or lab but you may not use the built-in search or sort method of other libraries. All code must be written by you!!!! It is important that you adhere to the framework specification above to facilitate testing of your program. What you need to turn in 1. Your DifferencePairs.java file (This should contain your findPairs method, as stated above and any additional method that you may use. 2. A .doc (or .rtf, .pdf, .txt, .docx) that contains two things a. Briefly describe your algorithm and determine the time efficiency of it. Don’t just say, for example, that my algorithm is O(nlogn), but explain how you got that time efficiency. Remember, don’t evaluate your code. That takes too long and will give you a headache. Instead, try to conceptualize how you are solving the problem and determine the Big-O that way. Pen and paper help with this.

Pair .java

package com.pairs; public class Pair { private int first; private int second; public Pair(int first, int last) { this.first = first; this.second= last; } public int getFirst() { return first; } public void setFirst(int first) { this.first = first; } public int getLast() { return second; } public void setLast(int last) { this.second = last; } public String toString() { return "(" + this.first + " , " + this.second+ ")"; } public boolean equals(Object other) { if(!(other instanceof Pair)) { return false; } Pair otherPair = (Pair)other; return this.first == otherPair.first && this.second == otherPair.second; } }

DifferencePairsJUnit.java

package com.pairs.test; import static org.junit.Assert.assertTrue; import org.junit.Ignore; import org.junit.Test; public class DifferencePairsJUnit { @Test public void test_empty_array() { int array[] = new int[0]; assert(DifferencePairs.findPairs(array, 10).length == 0); } @Test public void test_null() { int arr[] = null; assert(DifferencePairs.findPairs(arr, 1).length == 0); } @Test public void test_empty_array_of_single_element() { int array[] = new int[] { 5 }; assert(DifferencePairs.findPairs(array, 10).length == 0); } @Test public void test_single_pair_returned() { int array[] = new int[] { 5, 15 }; Pair result[] = DifferencePairs.findPairs(array, 10); Pair expectedResult[] = new Pair[] { new Pair(5, 15) }; assert(result.length == 1); assertTrue(compareArrays(result, expectedResult)); } @Test public void test_single_pair_returned2() { int array[] = new int[] { 5, 15 }; Pair result[] = DifferencePairs.findPairs(array, 10); Pair expectedResult[] = new Pair[] { new Pair(5, 15) }; assert(result.length == 1); assertTrue(compareArrays(result, expectedResult)); } @Ignore @Test public void student_created_test() { } private boolean compareArrays(Pair arr1[], Pair arr2[]) { if(arr1.length != arr2.length) { return false; } for(int i = 0; i < arr1.length; i++) { if(!arr1[i].equals(arr2[i])) { return false; } } return true; }

DiferencePairs.java

package com.pairs; public class DifferencePairs { public class QuickSort { public void sort(int arr[]) { sort(arr); // arr, first, last } private void quicksort(int[] arr, int first, int last) { //check if information is valid if(arr == null || arr.length <=1 || first >= last) { return; } //find pivot //find median int pivot = median(arr, first, last); //set temporary variables and set them to first and last int f = first; int l = last; //use while loop to sort the array while(f < l) { //f and l move index that are going to be moving stop when f and l cross over // go over here or there pick indexes that will swap // stop when element is greater than pivot item at f is greater than or equl to pivot // pivot value but f and l are indexes while(arr[f] < pivot ) { //move to the right f+=1; } while(arr[l] > pivot) { l -=1; } if(f <= 1){ swap(arr, f, l); f+= 1; l-=1; } } // Recursive part of the code if(first < l) { quicksort(arr, first, l); } if(last > f) { quicksort(arr, f, last); } } private void swap(int arr[], int idx1, int idx2) { int temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; } private int median(int[] arr, int first, int last) { // initialize the first, last and middle; int num1 = arr[first]; int num2 = arr[last]; int num3= arr[(first + last) / 2]; // finding maximum of 2 numbers if(num1 > num2 && num1 > num3) { return Math.max(num2, num3); }else if(num2 > num1 && num2 > num3) { return Math.max(num1, num3); }else { return Math.max(num1, num2); } } public Pair[] findPairs(int array[], int diff) { int n= array.length; quicksort(array,0,n-1); Pair pairs[]= newPair[]; for(int itr=0;itr

Explanation / Answer

Solution:

Please find the implementation below. However the equals() method provided here is just matching the places i.e. first with first & sec with second. But it should match two pair objects just on the basis of contents, because while filtering the array and populating the object Pair no such specification is there , for populating the instance variables in Pair object.

The method works with sample input given. Please do consider the equals(). The quick sort was also going into infinite loop, hence i have provided a simple quick sort algo, which you might wish to consider.

DifferencePairs.java

package com.pairs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DifferencePairs {

public static void sort(int[] inputArr) {

if (inputArr == null || inputArr.length == 0) {
return;
}
quickSort(inputArr, 0,inputArr.length - 1);
}

private static void quickSort(int[] array, int lowerIndex, int higherIndex) {

int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(array, lowerIndex, j);
if (i < higherIndex)
quickSort(array, i, higherIndex);
}

public static Pair[] findPairs(int array[], int diff) {
int n= array.length;
sort(array);
List<Pair> pairs = new ArrayList<Pair>();
for(int i=0; i< array.length -1 ; i++){
if(Math.abs(array[i + 1] - array[i]) == diff)
pairs.add(new Pair(array[i+1], array[i]));
}
//converting list to array
Pair[] pairArray = new Pair[pairs.size()];
for(int i =0; i< pairArray.length; i++)
pairArray[i] = pairs.get(i);
return pairArray;
}

/* public static void main(String [] args){
int[] arr = new int[]{10,4,6,16,1,6,12,13};
DifferencePairs pair1= new DifferencePairs();
System.out.println(Arrays.toString(pair1.findPairs(arr, 3)));
}*/
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.