Skip to main content
replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link

The version that @rolfl providesversion that @rolfl provides is that efficient. Your version is \$O(n^2)\$ which is asymptotically worse than my \$O(n \log n)\$ version even if it weren't buggy.

The version that @rolfl provides is that efficient. Your version is \$O(n^2)\$ which is asymptotically worse than my \$O(n \log n)\$ version even if it weren't buggy.

The version that @rolfl provides is that efficient. Your version is \$O(n^2)\$ which is asymptotically worse than my \$O(n \log n)\$ version even if it weren't buggy.

Source Link
mdfst13
  • 21.7k
  • 6
  • 33
  • 68

Bug

The output is wrong when firstNumber is equal to 1.

The problem is that you try to sort and count at the same time. So you count some occurrences more than once or not at all. Given this input, you count more than once more often than not at all.

Nitpick

    for(int i =0;i<array.length;i++)
    {
        if(i<numberOfOccurances)
        requiredArray[i]= firstNumber;
    }

You could write this more simply as

    for (int i = 0; i < numberOfOccurrences; i++)
    {
        requiredArray[i] = firstNumber;
    }

That saves you a comparison per loop iteration and reduces the number of iterations (unless the whole array is filled with that value). I also fixed the spelling of "Occurrences" and added additional whitespace for readability.

Use a Comparator for a custom sort

public class ExceptionFirstComparator implements Comparator<Integer> {

    private final int exception;

    public ExceptionFirstComparator(int i)
    {
        exception = i;
    }

    @Override
    public int compare(Integer a, Integer b)
    {
        if (a == exception)
        {
            if (b != exception)
            {
                return -1;
            }
        }
        else if (b == exception)
        {
            return 1;
        }

        return a.compareTo(b);
    }
}

Note that returning -1 means that a goes before b in the order while 1 means that b goes before a. A value of 0 is returned when the two are equal. For everything other than the exceptional value, the native form of the compareTo for Integer is correct. So we check the two exceptional cases first. If a and b are both equal to the exceptional value, then the native version works correctly. If only one is then that one goes first.

This solution throws a NullPointerException if either a or b are null. You could check for that instead, but I couldn't find a better exception to throw. The native behavior works just fine.

I use the block version of the if statements. This is more robust against bugs and I find it easier to read. I find the way that you put the then statement at the same level of indent as the if to be especially confusing. It's hard to tell that those statements only run conditionally. If you are going to use the single statement form, please either put them on the same line or use indent on the conditionally-run statement.

This isn't the most efficient solution for this particular problem. Counting the exceptions and moving them to the start of the array can be done in \$O(n)\$ time where \$n\$ is the length of the array. So the overall sort can be down to \$O(m + (n-m) \log (n-m))\$ time where \$m\$ is the number of exceptional values. Since \$\log(n-m)\$ is increasing and almost always going to be greater than one, this is asymptotically smaller than the \$O(n \log n)\$ time of this version.

The version that @rolfl provides is that efficient. Your version is \$O(n^2)\$ which is asymptotically worse than my \$O(n \log n)\$ version even if it weren't buggy.

What this solution is is extensible. If you have to define a different custom sort order, you just change the Comparator. This makes it easier and shorter to code. And for many other sort orders, there's no equivalent of the shortcut available here.

I'm not excited by the name ExceptionFirstComparator. Some other options are FreakFirstComparator and PrivilegedFirstComparator. Freak seems judgmental. Privileged would lead to the field being named something like privilegedValue. Exception is confusing in that Java already has exceptions with a somewhat different meaning. If these were people, I might try VipFirstComparator. But that doesn't really work for numbers.

I tested this with

    public static void main(String[] args) {
        Integer[] numbers = {1, 1, 0, 1, 2, 2, 0, 0};
        ExceptionFirstComparator comparator = new ExceptionFirstComparator(1);

        Arrays.sort(numbers, 0, numbers.length, comparator);

        for (int number : numbers) {
            System.out.println(number);
        }
    }

The result:

1
1
1
0
0
0
2
2

I used println rather than print as it saves a String concatenation. Not sure if that matters to the compiler, but I find it easier to code. Similarly, I used the for each form rather than manually indexing the array. Fewer moving parts means less danger of error.

I prefer to call an array of numbers numbers rather than array as I find it more descriptive.

It's more common to put { on the same line as the statement in Java. Not a huge deal if you're consistent, but I thought that I'd mention it.

Again, if run-time efficiency is your most important criterion, this solution is sub-par for this exact problem. But from a coding perspective, this is going to be easier to code initially and easier to modify later. And for many other problems, this is going to be more appropriate.