Sort an array by remainder of 4

Question

I have an exercise in which I have to sort an array in the following way:

1. the numbers that divide 4 with no remainder will be the first in the array (e.g 4,8,12,16).
2. the numbers that divide 4 with remainder of 1 will be the second in the array (1,5,9).
3. the numbers that divide 4 with remainder of 2 will be the third in the array (2,6,10).
4. the numbers that divide 4 with remainder of 3 will be last in the array.

For example, the following array:

int []a={1,7,3,2,4,1,8,14}

will be:

4   8   1   1   2   14  3   7   

the order within the groups does not matter.

I have found a solution which works on O(n) time complexity and O(1) space complexity.

However, it is ugly and moves on the array 3 times. I would want a more elegant solution.

This is my code:

    int ptr=a.length-1; int temp=0, i=0;
    while (i<ptr){
        //move 3 remained to the end
        if (a[i] % 4==3){
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==2)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==1)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }

Important to know:

• I don't want time complexity worse than O(n), and space complexity worse than O(1).

Answer 1

Since O(3 * N) is O(N), you only need to loop through the array three times:

1. Move the elements e % 4 == 0 to the front, swapping elements along the way;
2. Move the elements e % 4 == 1 to the front, swapping elements along the way;
3. Move the elements e % 4 == 2 to the front, swapping elements along the way;

The elements that e % 4 == 3 will be at the end after this.

Example:

public static void main(String args[]) {
    int[] a = { 1, 7, 3, 2, 4, 1, 8, 14 , 9};
    int current = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = current; j < a.length; j++) {
            if (a[j] % 4 == i) {
                int b = a[j];
                a[j] = a[current];
                a[current] = b;
                current++;
            }
        }
    }
    System.out.println(Arrays.toString(a));
}