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. Dont just say, for example, that my algorithm is O(nlogn), but explain how you got that time efficiency. Remember, dont 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; } } DifferencePairs.java package com.pairs; public class DifferencePairs { public Pair[] findPairs(int array[], int diff) { }