Sorting an array by residues from 4

Question

I have an exercise in which I have to sort the array as follows:

• numbers that divide 4 without a remainder will be the first in the array (for example, 4,8,12,16).
• numbers dividing 4 with a remainder of 1 will be the second in the array (1,5,9).
• numbers that divide 4 with the remainder of 2 will be the third in the array (2,6,10).
• numbers that divide 4 with a remainder of 3 will be the 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 

order within groups does not matter.

I found a solution that works on O (n) complexity and O (1) space complexity.

However, it is ugly and moves around the array 3 times. I would like to get 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++; } 

It's important to know:

• I do not want the complexity of time to be worse than O (n), and the complexity of space is worse than O (1).

Answer 1

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

• Move the elements e % 4 == 0 to the beginning, replacing the elements on this path;
• Move the elements e % 4 == 1 to the beginning, replacing the elements on this path;
• Move the elements e % 4 == 2 to the beginning, replacing the elements on this path;

Elements that e % 4 == 3 will be at the end after that.

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)); } 

Answer 2

You can use more memory. This is not true, but I will put it anyway.

 int modulusLength = 4; List<Integer> array[] = new List<Integer>[modulusLength]; for(int i = 0; i < modulusLength; i++) array[i] = new ArrayList<Integer>; for(int i = 0 ; i < a.length; i++) array[a[i]%modulusLength].put(a[i]); int counter = 0; for(int i = 0 ; i < array.length; i++) for(int j = 0; j < array[i].size; j++) { a[counter] = array[i].get(j); counter++; } 

Horrible and scary, but it was fun to write. And it works :)

Answer 3

Just use a comparator and use for a very efficient internal sorting algorithm.

 Arrays.sort(a, new Comparator() { public int compare(int a, int b) { if(a%4 == b%4) { if(a < b) return -1; if(a > b) return 1; return 0; } else { if(a%4 < b%4) return -1; if(a%4 > b%4) return 1; return 0; } } });