Subsets - Difference in Pairs

[Naziru Gelajo]

Hello all,

I am trying to write a program that takes an array, effectively sorts the array with quickSort, then for each pair in the sorted array with a specified distance passed by reference (via the parameter in the method), it adds the difference to an ArrayList. The method effectively returns an ArrayList with integer pairs that are different. Please let me know if you need further clarification. For some reason, my code is returning an error in memory (in fact sometimes it does not even run). Now, from my understanding quicksort is the sort to use if the program does not use memory. However, if the program uses a substantial amount of memory, one should use Merge Sort. Please tell me where I'm going wrong. Thanks!

import java.util.ArrayList;

public class DifferencePairs {
	public static ArrayList<Pair> findPairs(int[] array, int diff) {
		/*
		 * sort the array. This takes O(n log n) (quicksort)
Then for each x in array A, use binary search to look for difference in elements. This will take O(logn).
So, overall search is  O(n log n)
		 */
		sort(array);
		int i = 0;
		int j = 1;
		int sizeOfArray = array.length;
		
		ArrayList<Pair> differencePairs = new ArrayList <Pair>();
		while (i < sizeOfArray && j < sizeOfArray) {
			if (i != j && (array[j] - array[i] == diff)) {
				
				Pair newPair = new Pair(array[j], array[i]);
				differencePairs.add(newPair);
			} else if (array[j] - array[i] < diff) {
				j++;
			} else if (array[j] - array[i] > diff){
				i++;
			
			}
		} return differencePairs;
		
	}
	
	
	public static void sort(int[] arr)
    {
        quickSort(arr, 0, arr.length - 1);
    }
    /** Quick sort function **/
    public static void quickSort(int arr[], int low, int high) 
    {
        int i = low, j = high;
        int temp;
        int pivot = arr[(low + high) / 2];
 
        /** partition **/
        while (i <= j) 
        {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) 
            {
                /** swap **/
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
 
                i++;
                j--;
            }
        }
 
        /** recursively sort lower half **/
        if (low < j)
            quickSort(arr, low, j);
        /** recursively sort upper half **/
        if (i < high)
            quickSort(arr, i, high);
    }
    
    public static void main(String[] args) {
    		int[] myArray = {16, 12, 7, 8, 4, 13, 9, 20};
    		ArrayList<Pair> pairs = findPairs(myArray, 4);
    		for (Pair pair: pairs) {
    			System.out.println(pair.toString());
    		}
    }
    
    
}

The error being generated comes from my main method where I initiate an improved for loop to print out Pairs from the declared arraylist. It is not running right now for example.

[Naziru Gelajo]

In case if you ladies and gentlemen are wondering, here is the error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:3210)
at java.util.Arrays.copyOf(Arrays.java:3181)
at java.util.ArrayList.grow(ArrayList.java:261)
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
at java.util.ArrayList.add(ArrayList.java:458)
at DifferencePairs.findPairs(DifferencePairs.java:20)
at DifferencePairs.main(DifferencePairs.java:72)

This is the Pair class:

public class Pair {
	
	private int first;
	private int last;
	
	public Pair(int first, int last)
	{
		this.first = first;
		this.last= last;
		
	}
	public int getFirst() {
		return first;
	}

	public void setFirst(int first) {
		this.first = first;
	}

	public int getLast() {
		return last;
	}

	public void setLast(int last) {
		this.last = last;
	}

	public String toString()
	{
		return "(" + this.first + " , " + this.last+ ")";
	}
	

}

[Campbell Ritchie]

Naziru Gelajo wrote:. . . specified distance passed by reference (via the parameter in the method)

There ain't no such thing as pass by reference in Java®.

. . . quicksort is the sort to use if the program does not use memory. However, if the program uses a substantial amount of memory, one should use Merge Sort.

What does that mean and where did you get it from? Do you mean that merge sort requires lots of memory to be executed? There are different reasons for choosing quicksort or merge sort.

Please tell me where I'm going wrong. Thanks!
. . . The error being generated comes from my main method where I initiate an improved for loop to print out Pairs from the declared arraylist. It is not running right now for example.

Don't know. I think it very unlikely that you are running out of memory in that for‑each loop. You must be creating an infinite recursion somewhere. Try putting some print statements in the main method so you know how far your program has got before you run out of memory.

You don't need to write pair.toString(); simply writing System.out.println(pair) will implicitly call its toString method. It is safer that it won't throw an Exception if pair is null.

[Campbell Ritchie]

The stack trace for that exception suggests you are trying to add so many pairs to the List that you are exhausting the memory available.

[Naziru Gelajo]

Campbell Ritchie wrote:
. . . The error being generated comes from my main method where I initiate an improved for loop to print out Pairs from the declared arraylist. It is not running right now for example.

Don't know. I think it very unlikely that you are running out of memory in that for‑each loop. You must be creating an infinite recursion somewhere. Try putting some print statements in the main method so you know how far your program has got before you run out of memory.

You don't need to write pair.toString(); simply writing System.out.println(pair) will implicitly call its toString method. It is safer that it won't throw an Exception if pair is null.

Hello Campbell, apologies for some of those extremely vague explanations. What I meant by quickSort and its memory constraints is that one uses quickSort if the algorithm will fit in memory. One uses MergeSort if external storage is needed. Although both algorithms are technically O(n log n) average case, quick sort is still faster.

With that said, I will follow your advice. Thanks!

[Campbell Ritchie]

Naziru Gelajo wrote:. . . . What I meant by quickSort and its memory constraints is that one uses quickSort if the algorithm will fit in memory. One uses MergeSort if external storage is needed. Although both algorithms are technically O(n log n) average case, quick sort is still faster.

That sounds incorrect. Both can use built‑in memory, but merge sort requires more memory for its intermediate stages. There is another reason why you might want to use merge sort in preference to quicksort. Look at this method and this one.

. . . Thanks!

[edit] Forgot to say, That's a pleasure