Using an InsertionSort algorithm to sort an Array of Strings with null elements within them

Question

The algorithm formulated here has a complexity of O(n^2) (insertion sort). The algorithm though gets a NullPointerException since there are null elements within the String array. How do I get my algorithm to sort an array with null elements? Algorithm below:

private void sortFlowers(String flowerPack[]) {
    // TODO: Sort the flowers in the pack (No need to display
    // them here) - Use Selection or Insertion sorts
    // NOTE: Special care is needed when dealing with strings!
    // research the compareTo() method with strings

    String key;

    for (int j = 1; j < flowerPack.length; j++) { //the condition has changed
        key = flowerPack[j];
        int i = j - 1;

        while (i >= 0) {
            if (key.compareTo(flowerPack[i]) > 0) { //here too
                break;
            }

            flowerPack[i + 1] = flowerPack[i];

            i--;
        }

        flowerPack[i + 1] = key;
    }
}

Jameson · Accepted Answer · 2016-10-23 01:10:50Z

3

If key can be null, then you should change this condition:

key.compareTo(flowerPack[i]) > 0

To something like:

compareKeys(key, flowerPack[i]) > 0

And then add a null-safe check, like:

private int compareKeys(final String first, final String second) {
    if (first == null || second == null) {
        return 0; // TODO: 0, here?
    } else {
        return first.compareTo(second);
    }
}

answered Oct 23, 2016 at 1:10

Jameson

6,7296 gold badges37 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

David Ehrmann · Accepted Answer · 2016-10-23 01:09:48Z

1

compareTo() is part of the Comparable interface. It doesn't have a defined behavior for comparing null to anything. It actually can't have that behavior because a.compareTo(b) and b.compareTo(a) need to be consistent. You can:

1) Implement a custom Comparator that knows how to compare nulls, then replace key.compareTo(flowerPack[i]) with myComparator.compare(key, flowerPack[i])

2) Not use nulls.

3) Since this looks like homework, rewrite the bit inside your while look to only use compareTo() if both key and flowerPace[i] are non-null. If either (or both) are null, you need special cases.

answered Oct 23, 2016 at 1:09

David Ehrmann

7,6143 gold badges35 silver badges46 bronze badges

Collectives™ on Stack Overflow

Using an InsertionSort algorithm to sort an Array of Strings with null elements within them

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related