Check if a list of ints is pairwise sorted

Question

In class we created our own ArrayList class; the code I wrote is meant to interact with the ArrayIntList class. I'm looking for general feedback to help with the next time I write code. I'm also wondering if it's "safe" to change the value of the size variable in my method (size represents the current size of the ArrayIntList.)

Write a method isPairwiseSorted that returns whether or not a list of integers is pairwise sorted (true if it is, false otherwise). A list is considered pairwise sorted if each successive pair of numbers is in sorted (non-decreasing) order. For example, if a variable called list stores the following sequence of values:

[3, 8, 2, 5, 19, 24, -3, 0, 4, 4, 8, 205, 42]

Then the call of list.isPairwiseSorted() should return true because the successive pairs of this list are all sorted: (3, 8), (2, 5), (19, 24), (-3, 0), (4, 4), (8, 205). Notice that the extra value 42 at the end had no effect on the result because it is not part of a pair. If the list had instead stored the following:

[1, 9, 3, 17, 4, 28, -5, -3, 0, 42, 308, 409, 19, 17, 2, 4]

Then the method should return false because the pair (19, 17) is not in sorted order. If a list is so short that it has no pairs, then it is considered to be pairwise sorted. If a list is of odd length, the final element should be ignored since it has no pair. In other words, if the rest of the list is pairwise sorted until that last unpaired element, your method should return true.

Assume you are adding to the ArrayIntList class with following fields:

public class ArrayIntList {
    private int[] elementData;
    private int size;

   // your code goes here
}

And here's my code:

public boolean isPairwiseSorted() {
    if (size <= 1) {
        // Pairwise sorted for lists smaller than two elements
        return true;
    }
    boolean reIncrementSize = false;
    if (size % 2 != 0) {
        reIncrementSize = true;
        size--;
    }
    for(int i = 0; i < size; i+=2) {
        // Pairwise sorted if elements are in increasing order
        if (elementData[i] > elementData[i + 1]) {
            return false;
        }
    }
    if (reIncrementSize) {
        size++;
    }
    return true;
}

Answer 1

    if (size <= 1) {
        // Pairwise sorted for lists smaller than two elements
        return true;
    }

Special cases are sometimes useful, but KISS: does this simplify the code or make it more complex for no benefit?

---

    boolean reIncrementSize = false;
    if (size % 2 != 0) {
        reIncrementSize = true;
        size--;
    }

....

    if (reIncrementSize) {
        size++;
    }

Yikes! It really shouldn't be necessary to make temporary changes to the state of the class. But if you really absolutely have to do it, you should use try ... finally to guarantee that they are undone. Here the temporary changes introduce a bug: if we hit the return false then the size is permanently decremented.

---

    for(int i = 0; i < size; i+=2) {
        // Pairwise sorted if elements are in increasing order
        if (elementData[i] > elementData[i + 1]) {
            return false;
        }
    }

Why was size temporarily decremented? I presume it's to avoid an out of bounds array access in elementData[i + 1]. But you can do that just as well by making that be the guard condition:

    for(int i = 0; i + 1 < size; i+=2) {

Answer 2

    boolean reIncrementSize = false;
    if (size % 2 != 0) {
        reIncrementSize = true;
        size--;
    }

You make a new variable just to track whether or not you made a change. Consider instead

    int pairedSize = (pairedSize % 2 == 0) ? size : size - 1;

Now you can just change

    for(int i = 0; i < size; i+=2) {

to

    for (int i = 0; i < pairedSize; i += 2) {

and remove

    if (reIncrementSize) {
        size++;
    }

The temporary variable will just go away. You don't need to update it.

We don't know exactly how a compiler might optimize things, but consider that if size is stored in memory, it will still need to be loaded into something that the processor can access directly. So we can load size into a register, update that register, and then not save the register back to size. That's less work than what this does.

It should be obvious that your method is not thread safe. If size were accessed while this method was run, its value might not match what it should be.

There are times when it makes sense to update and then restore, but this doesn't seem to be one of them. Even if you fixed the error where you return without restoring, there are other hazards. And this is more work.

You want the change to be temporary and have to make a temporary variable regardless. So just make the temporary change to the temporary variable. That gives you the exact change that you want without extra scaffolding to make it work. The code is both shorter and more robust.

This is also more readable. Now someone can see that our new value is a pairedSize, which is always even.

        // Pairwise sorted if elements are in increasing order
        if (elementData[i] > elementData[i + 1]) {
            return false;
        }

The comment doesn't match the code. Consider instead

        if (elementData[i] > elementData[i + 1]) {
            // Not pairwise sorted if elements are in decreasing order
            return false;
        }

The other statement was true but confusing in that it didn't describe the code that followed.

And actually, it might be easier to read without the comment altogether. Then we are returning false from a method named isPairwiseSorted because the ith element is greater than the next element. That should tell us that it is not pairwise sorted if decreasing.

Where you should have had a comment in the original code was for reIncrementSize. That's confusing in that you set it one place and make use of it in a different place while the true effect is the temporary change in size.