# CSC 385 SORTING ASSIGNMENT Solved

40.00 \$ 20.00 \$

Category:

## Description

Finding All Pairs of Elements with a Given Difference in an Array
Problem Definition:

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:
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.
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.      Create a class called DifferencePairs, to contain your algorithm and associated methods and attributes.
2.      In your DifferencePairs class, encapsulate your algorithm within a method called findPairs, with the signature:
public Pair[] findPairs(int array[], int diff)
3.      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.
4.      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.