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

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 2

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.