Array sorting effective

Question

For a homework assignment, I need to write method which can sort array, the sort method should be efficient as possible.

1. Beginning of the array will appear all the numbers that divide by 4 without remainder.
2. Will be followed by all the numbers that divide by 4 with remainder of 1
3. Will be followed by all the numbers that divide by 4 with remainder of 2
4. At the end of the array will all the other numbers (those that divide by four with the remaining three).

I tried this set 4 pointers:
2 pointers At first the remainder of 0 and 1
2 pointers at the last of the array for the remainder of 2 and 3

This is what I could find so far (with problem of course), I appreciate your help !

public static void sortByFour (int[] arr)
{
    int temp;
    int noRemainderIndex = 0;
    int remainder1Index = 1;
    int remainder2Index = arr.length - 2;
    int remainder3Index = arr.length - 1;

    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] % 4 == 0)
        {
            temp = arr[noRemainderIndex];
            arr[noRemainderIndex] = arr[i];
            arr[i] = temp;
            noRemainderIndex++;
            remainder1Index++;
        }
        else if (arr[i] % 4 == 1)
        {
            temp = arr[remainder1Index];
            arr[remainder1Index] = arr[i];
            arr[i] = temp;
            remainder1Index++;
        }
        else if (arr[i] % 4 == 2)
        {
            temp = arr[remainder2Index];
            arr[remainder2Index] = arr[i];
            arr[i] = temp;
            remainder2Index--;
        }
        else if (arr[i] % 4 == 3)
        {   
            temp = arr[remainder3Index];
            arr[remainder3Index] = temp = arr[i];
            arr[i] = temp;
            remainder3Index--;
            remainder2Index--;
        }
    }

Answer 1

Hints for your homework.

1. If you are allowed to use existing library methods, look at Array.sort(...) and the Comparator interface. (Noting that to use a custom comparator when sorting an array of a primitive type, you have to convert to the wrapper type first; e.g. convert int[] to Integer[], sort, and convert back.)

2. If you are not allowed to use Array.sort(...) (or similar), figure out if this is a sorting problem or a collating problem. In other words if there is any requirement to reorder (or retain the order of) the numbers in the 4 categories.

3. You could simplify the problem by using 4 temporary arrays, but there are other (more tricky) solutions that involve making multiple passes through the array and swapping pairs of elements.

4. One of the problems that needs to be solved is that you don't know beforehand how many numbers there are in each of the 4 categories. So you don't know beforehand the destinations for moving the numbers. But there are solutions to this ...

---

... the sort method should be efficient as possible.

Is this a homework requirement, or your requirement?

If this is something that you've added yourself - BEWARE - your marker may give higher marks for a simple solution than a (supposedly) more efficient but overly complicated solution.

A good software engineer does not strive for the ultimate in efficiency in every program. Rather, he balances various things:

• functionality requirements,
• requirements for performance,
• requirements for software maintainability, and
• project deadlines,

noting that some of these requirements may be implied, and / or not properly understood by management.

(Or to put it another way, a program that is fast .... but doesn't work reliably, or isn't maintainable, or isn't ready in time ... is a failure.)

On the other hand, if performance is a requirement for this homework exercise, then your lecturers should have explained how to measure performance of small program in Java. (Trust me ... this is NOT a simple thing to do.) You need to apply this to your homework problem to decide which of the alternative solutions is fastest.

Answer 2

I think you want something similar to partition algorithm used in quicksort.

4 pointers is a good start, but let me change their functions:
1) points to the end of remainder = 0
2) points to the end of remainder = 1
3) points to the end of remainder = 2
4) points to the start of unclassified

The array is split into 5 parts: remainder = 0, 1, 2, 3 and unclassified.

If remainder = 3, just increment the pointer 4. The number if included in remainder = 3 group.
If remainder = 2, increment the pointer 3 and swap the current value with the value at pointer 3. Increment pointer 4.
If remainder = 1, increment the pointer 2, swap with current value; increment the pointer 3, swap with current value. Increment pointer 4.
If remainder = 0, well, do the swapping 3 times.

Answer 3

Why don't you create a custom class which holds two values, the number and the remainder. Create an array of this mini class, pass the values and pre-calculate your remainder. This will help you on not having to re-calculate the remainder every time you pass through an element of your list. You have to move and sort your elements based on the remainder property.

Then you have a classic problem of sorting a list with only few unique elements. The performance of the sorting algorithm you choose depends on the initial condition. I might say the best option is the Shell sorting algorithm or the Quick3.

http://www.sorting-algorithms.com/few-unique-keys

Answer 4

I think a better way to do this would be to have 4 arrays, one for each case. Treat each array as a queue. Iterate through the array and push onto the respective arrays. Once that is done, just append the arrays to each other. A very clean solution.