-1

I am currently trying to implement a Merge Sort algorithm in Java based on the one found in Introduction to Algorithms: Third Edition. The authors use a divide and conquer algorithm that also implements sentinel cards (here is pseudo code). These cards are supposed to have a value of infinity, but since I am using an array of strings, I assumed that the value would be null. Apparently that is not the case because when I try comparing L[i] and R[j] I get a Null Pointer Exception. Here is my code:

public static void main(String[] args) {
    Scanner textfile = new Scanner(System.in);
    System.out.println("Enter a filename: ");
    String fileName = textfile.nextLine();
    String[] words = readArray(fileName);
    mergeSort(words, 0, words.length - 1);
    for (String word : words) {
        System.out.println(word);
    }

}

public static String[] readArray(String file) {
    int ctr = 0;
    try {
        Scanner s1 = new Scanner(new File(file));
        while (s1.hasNextLine()) {
            ctr = ctr + 1;
            s1.nextLine();
        }
        String[] words = new String[ctr];
        Scanner s2 = new Scanner(new File(file));
        for(int i = 0; i < ctr; i++) {
            words[i] = s2.next();
        }
        return words;
    }
    catch (FileNotFoundException e){
        System.out.println("File not found.");
    }
    return null;
}

public static void mergeSort(String[] A, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

public static void merge(String[] A, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;

    String[] left = new String[n1 + 1];
    String[] right = new String[n2 + 1];

    for (int i = 0; i < n1; i++) {
        left[i] = A[p + i];
    }

    for (int j = 0; j < n2; j++) {
        left[j] = A[q + j + 1];
    }
    left[n1] = null;
    right[n2] = null;
    for (int i = 0, j = 0, k = p; k < r; k++) {
        if (left[i].compareTo(right[j]) <= 0) { \\Null Pointer Exception
            A[k] = left[i];
            i++;

        } else {
            A[k] = right[j];
            j++;

        }
    }
}

So what's the problem? Is it because I declared the two arrays as null? I tried things like "zzzz" and still get the same problem. Or am I completely missing something else? Also, the pseudo code assumes that the array starts at index 1, which is why there are slight changes in my code. Did I do something wrong there?

poniboy4
  • 19
  • 5
  • 1
    "*I assumed that the value would be null. Apparently that is not the case because when I try comparing L[i] and R[j] I get a Null Pointer Exception.*" Wait, are you being serious here? You declared the value as null and so it threw a null point exception, I don't see the problem. – Riley Carney Feb 02 '16 at 00:07
  • Possible duplicate of [What is a Null Pointer Exception, and how do I fix it?](http://stackoverflow.com/questions/218384/what-is-a-null-pointer-exception-and-how-do-i-fix-it) – John3136 Feb 02 '16 at 00:08
  • There's practically no Java string that's guaranteed to compare greater than any other string (and thus be suitable as a sentinel) so you could just test for i == n1 and j == n2. – Klitos Kyriacou Feb 02 '16 at 00:10
  • @Riley Yeah, that does sound dumb. I only said that because I found [this](https://peace.csi.muohio.edu/trac/peace/browser/release-0.95/EAST/Java/src/com/mhhe/clrs2e/MergeSort.java). And when I use `compare()` it gives me an out of bounds exception on the same line. Sorry, I've just been at this all day. – poniboy4 Feb 02 '16 at 00:17
  • Do you mean the `compare()` method on the last line of the class you linked? From what I see, it should work. When I looked at the `compareTo()` in the `String` class, it says it throws a `NullPointException` whenever a null value is passed in. – Riley Carney Feb 02 '16 at 00:25
  • I also looked at the `compareTo()` in the `Comparable` class (which they are using in the code) and it throws a `NullPointException` as well. https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html https://docs.oracle.com/javase/7/docs/api/java/lang/String.html – Riley Carney Feb 02 '16 at 00:31
  • @poniboy4: I can see you have been at it all day, when you write in the question: 'I tried things like "zzzz"' :) – Aravind Feb 02 '16 at 02:37

1 Answers1

0

You're infinity-String must fulfill the following-property:

s.compareTo(infinityString) == -1

for any s, if you want to use String#compareTo. That being said infinityString = null doesn't yield the required properties, since it produces a NullPointerException if either in this code a.compareTo(b) either a or b is infinityString. There would be the really ugly workaround of simply using a sufficiently long String of arbitrary characters, such that there exists no equally long String in the input. But that's:

  • a really ugly and insecure hack
  • a waste of memory

Instead I'd recommend using one of these two approaches:

  • use your own comparison-method instead of String#compareTo, that yields the property compare(s , infinityString) = -1 for whatever you want to define infinityString to be.
  • use an implementation of merge-sort without sentinel cards and simply eliminate the need for an infinity-element.