Sort array of Numbers with some values always first

Question

The first number will be dynamically selected and remaining array should be sorted ascending

    int[] array = {1,1,0,1,2,2,0,0};
    int  firstNumber = 0;// dynamic can be 0 or 1 or 2
    int numberOfOccurances = 0;

    //Basic sort functionality
    for(int i = 0 ; i< array.length; ++i)
    {
        if(array[i] == firstNumber)
        {
            numberOfOccurances++;
        }
        for(int j = i+1; j<array.length; ++j)
        {   
            if(array[j] < array[i])
            {   
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    int[] requiredArray= new int[array.length]; 
    for(int i = array.length-1 ; i >= 0; i--)
    {
        if(array[i] != firstNumber)
        requiredArray[i] = array[i];

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

    //Print Output
    for (int i = 0; i<requiredArray.length; i++)
    System.out.print(requiredArray[i] + "  ");

Output:

1 1 1 1 0 0 2 2

I was able to get desired output. But not sure if this is the best way to solve in terms of speed.

Answer 1

This can be easily done using a two-phase approach, one to shift values to the front that you want to keep, the other to sort the remainder.

Note, for sorting, use the native functions in the libraries... in this case, Arrays.sort(...)

It would also be much better to wrap this up in a function, taking 2 arguments, the number to put first, and the array to sort.

public static void sortFirst(int first, int[] array) {
    int left = 0;
    for (int right = 0; right < array.length; right++) {
        if (array[right] == first) {
            // swap left and right... put the first values first.
            array[right] = array[left];
            array[left] = first;
            left++;
        }
    }

    // OK, now we have "left" pointing to the actual data that needs sorting
    Arrays.sort(array, left, array.length);
}

Answer 2

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.