Sorting arrays in Java

Question

Write a static method in Java:

public static void sortByFour (int[] arr)

That receives as a parameter an array full of non-negative numbers (zero or positive) and sorts the array in the following way:

• In the beginning of the array all the numbers that are divisible by four will appear.

• After them all the numbers in the array that divide by 4 with a remainder of 1 will appear.

• After them all the numbers in the array that divide by 4 with a remainder of 2 will appear.

• In the end of the array all the rest numbers (those which divide by 4 with the remainder 3) will appear.

(The order of the numbers in each group doesn't matter.)

The method must be as efficient as possible.

The following is what I wrote, but unfortunately it doesn't work well... :(

public static void swap( int[] arr, int left, int right )
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

public static void sortByFour( int[] arr )
{
    int left = 0;
    int right = ( arr.length - 1 );
    int mid = ( arr.length / 2 );
    while ( left < right )
    {
        if ( ( arr[left] % 4 ) > ( arr[right] % 4 ) )
        {
            swap( arr, left, right );
            right--;
        }
        if ( ( arr[left] % 4 ) == ( arr[right] % 4 ) )
            left++;
        else
            left++;
    }
}

How do I fix or rewrite my code so that it will work well?

Answer 1

Read this page. http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms

That should help you best in the long run. It's also pretty fun!

Answer 2

I will do this in psuedocode for you but doing it in code would be giving you the answer and this is homework so you can do your own work. =P

Here is how to do it without lists. This example is restricted based on the requirements but will work once you code it.

int bucketSize = (arr.length() / 4) + 1;

int bucket1[bucketSize];
int bucket2[bucketSize];
int bucket3[bucketSize];
int bucket4[bucketSize];

for (int i=0; i<arr.length; i++) {
    if ((arr[i] % 4) == 0)
        put arr[i] in bucket 1
    else if ((arr[i] % 4) == 1)
        put arr[i] in bucket 2
    else if ((arr[i] % 4) == 2)
        put arr[i] in bucket 3
    else
        put arr[i] in bucket 4
}

for (int i=0; i<4; i++) {
    this will go for each bucket
    for (int j=0; j<bucketSize; j++) {
        do sort of your choice here to sort the given bucket
        the sort you used in your code will do fine (the swapping)
    }
}

then concatenate the four buckets in their respective order to get your end result

Answer 3

You can attack the problem like this:

1. Select a sorting algorithm that you wish to use. It looks like you are trying to program Quicksort, but you could also use Bubble Sort.
2. Identify the point(s) of the algorithm where two values from the input array are being compared. For example, in the pseudocode for Bubble Sort on the Wikipedia article, the only comparison is the line if A[i] > A[i+1] then....
3. Figure out a way to compare two numbers so that a number s having remainder 0 when divided by 4 is considered less than a number t having remainder 1 when divided by 4. Replace the comparison operations of the algorithm with your comparator calculation (e.g. if myIsGreater(A[i], A[i+1]) then...).

For step 3, you are definitely on the right track by considering the modulus operator.

Answer 4

I will reiterate what Daniel said: you have your choice of sorting algorithm. Use the most efficient one that you've covered in the class so far, if that is the requirement. But when you get to the point in your algorithm where two items are being compared, compare their value mod 4 instead. So something like if A[i] > A[j] becomes if A[i] % 4 > if A[j] % 4. Then you continue doing whatever the algorithm specifies that you do with that array element. Swap it, bubble it up, return it, whatever is called for.

Regarding the code that you posted, I don't think that it lends itself to a quick fix. Which algorithm is it supposed to be using? What is mid there for? I think that once you know which algorithm you intend to use, and figure out which line of code contains the comparison, you will be able to quickly see and code a solution.

In general, with these sorts of things, it can help if you focus on getting a working solution before you worry about efficiency. I used selection sort the first time I had to do a problem like this. I would recommend trying that first, and then using the experience gained to do one with merge sort, which is O(n log n).

Answer 5

A linear-time solution

The most asymptotically efficient way to do this would be to use bucket sort.

• You have 4 buckets, one for each of the congruency class of numbers modulo 4.
• Scan the numbers in the array once
  • Put each number in the right bucket
• Then construct the output array
  • Put all numbers from bucket 0 first, then all from bucket 1, then bucket 2, then bucket 3

Thus, this sorts the numbers in O(N), which is optimal. The key here is that by sorting on numbers modulo 4, there are essentially only 4 numbers to sort: 0, 1, 2, 3.

---

An illustrative solution with List

Here's an implementation of the above algorithm (for general modulo M) using List and for-each for clarity. Ignore the unchecked cast warning, just concentrate on understanding the algorithm.

import java.util.*;

public class BucketModulo {
    public static void main(String[] args) {
        final int M = 4;
        List<Integer> nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5);
        List<Integer>[] buckets = (List<Integer>[]) new List[M];
        for (int i = 0; i < M; i++) {
            buckets[i] = new ArrayList<Integer>();
        }
        for (int num : nums) {
            buckets[num % M].add(num);
        }
        nums = new ArrayList<Integer>();
        for (List<Integer> bucket : buckets) {
            nums.addAll(bucket);
        }
        System.out.println(nums);
        // prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]"
    }
}

Once you fully understand the algorithm, translating this to use arrays (if you must) is trivial.

See also

• java.util.List<E> API - "An ordered collection"
  • add(E e) - "Appends the specified element to the end of this list"
  • addAll(...) - "Appends all of the elements in the specified collection to the end of this list"
• Java Language Guide/The for-each Loop (introduced in 1.5.0)

---

A special note on %

The stipulation that numbers are non-negative is significant, because % is NOT the modulo operator as it's mathematically defined; it's the remainder operator.

System.out.println(-1 % 2); // prints "-1"

References

• JLS 15.17.3 Remainder Operator %
• Wikipedia/Modulo operation

Answer 6

Here's a Java-ish way...

    Arrays.sort(arr,new Comparator<Integer>(){
      public int compare(Integer a,Integer b)
      {
        return (a % 4) - (b % 4);
      }
    });